# Project Euler Problem 46 Solution

## 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?

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