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.000s

Python

#!/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.008s

Ruby

#!/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