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^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
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?
In [1]:
def primes_less_than_n(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
max_num_digits = 5
primes = primes_less_than_n((10**max_num_digits+1)-1)
print len(primes)
s_primes = set(primes)
def is_prime(p):
return p in s_primes
In [2]:
import math
for i in range(1,10**5):
o = 2*i + 1
if is_prime(o):
continue
found = False
for p in primes:
if p > o:
break
t = math.sqrt((o - p)/2.0)
if abs(t - math.floor(t)) < 1e-10:
found = True
break
if not found:
print o
break