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{align} 9 = 7 + 2 \times 1^2\\ 15 = 7 + 2 \times 2^2\\ 21 = 3 + 2 \times 3^2\\ 25 = 7 + 2 \times 3^2\\ 27 = 19 + 2 \times 2^2\\ 33 = 31 + 2 \times 1^2 \end{align}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?
One approach to this problem incorporates the sieve of Eratosthenes (cf. Problem 7) in a pretty slick way.
For every odd number between 3 and some cap \(C\), we keep track of two Boolean variables: whether it's prime (true by default), and whether it satisfies the conjecture (false by default). We update these variables by iterating through the odd numbers in order. For each odd \(n\), we check if it's composite and fails the conjecture, and return it if so. Otherwise, if \(n\) is prime, we mark its multiples starting from \(n^2\) as composite per the sieve, and then mark all \(n + k^2 \leq C\) as satisfying the conjecture.
from math import isqrt
def p46():
C = 10**5 # this is large enough
# It's faster to just ignore the even indices
is_prime = [True for n in range(C)]
satisfies_conjecture = [False for n in range(C)]
for n in range(3, C, 2):
if is_prime[n]:
for m in range(n**2, C, n):
is_prime[m] = False
for k in range(1, isqrt((C-n)//2)):
satisfies_conjecture[n+2*k**2] = True
elif not satisfies_conjecture[n]:
return n