# Problem 46

^{3}/ Nov 2008

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 212

15 = 7 + 222

21 = 3 + 232

25 = 7 + 232

27 = 19 + 222

33 = 31 + 212

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?

Goldbach予想か。

check n =all (not.isPrime). takeWhile(>) .map (x->n-2*x*x)$ [..] p046 = head.filter check$ [3,5..] sieve (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=).(`mod` p)) qs')) where (ps',qs') = span (<p*p) qs primes = iterate sieve([2],([3],[3,5..]))>>=fst isPrime ::Integer->Bool isPrime 1 = False isPrime n@(m+1) = isP primes n where isP (p:ps) n | n < p*p = True | mod n p == = False | otherwise = isP ps n