Problem Description

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 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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

Analysis

Generate primes as needed and check the conjecture until a prime isn’t found.

Solution

Runs < 1 second in Python.

n = 5
f = 1
primes = set()
 
while (1):
  if all( n % p for p in primes ):
    primes.add(n)
  else:
    if not any( (n-2*i*i) in primes for i in xrange(1, n) ):
      break
  n += 3-f
  f = -f
print "Answer to PE46 = ", n

Comments