Question
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
\begin{aligned} 9 & = 7 + 2\times1^2 \\ 15 & = 7 + 2\times2^2 \\ 21 & = 3 + 2\times3^2 \\ 25 & = 7 + 2\times3^2 \\ 27 & = 19 + 2\times2^2 \\ 33 & = 31 + 2\times1^2 \end{aligned}
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Haskell
isPrime :: Integer -> Bool
isPrime n | n < 1 = False
| otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]]
isSum :: Integer -> Bool
isSum n = any isPrime [n - 2*s^2 | s <- [0..floor $ sqrt $ fromInteger n]]
candidates :: [Integer]
candidates = [n | n <- [1,3..], not (isPrime n), not (isSum n)]
main :: IO ()
main = print $ head candidates$ ghc -O2 -o goldbach goldbach.hs
$ time ./goldbach
real 0m0.011s
user 0m0.011s
sys 0m0.000sPython
#!/usr/bin/env python
from itertools import product
def sieve(n):
numbers = list(range(2, n+1))
p = 2
j = 0
done = False
while not done:
for i, n in enumerate(numbers):
if n % p == 0 and n!=p:
numbers.pop(i)
j += 1
p = numbers[j]
if p**2 > n:
done = True
return numbers
def main():
primes = sieve(10000)
composites = set(n for n in range(2,10000) if n not in primes)
twicesquares = set(2*(n**2) for n in range(100))
sums = set(sum(c) for c in product(primes, twicesquares))
print(min(n for n in composites if n not in sums and n % 2 != 0))
if __name__ == "__main__":
main()$ time python3 composite-prime.py
real 0m0.226s
user 0m0.218s
sys 0m0.008sRuby
#!/usr/bin/env ruby
require 'set'
require 'mathn'
primes = (2..10000).select { |n| n.prime? }.to_set
composites = (2..10000).reject { |n| n.prime? }.to_set
twicesquares = (0..100).map { |n| 2*(n**2) }.to_set
sums = primes.to_a.product(twicesquares.to_a).map { |a,b| a+b }.to_set
puts composites.select { |n| !sums.include?(n) and n.odd? }.min$ time ruby composite-prime.rb
real 0m0.104s
user 0m0.104s
sys 0m0.000s