Project Euler Problem 46: Goldbach’s Other Conjecture

The source code for this problem can be found here.

Problem Statement

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{split}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{split}\]

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?

Solution Discussion

Iterate through all odd composite numbers \(k\) in ascending order and search for a solution of the form:

\[k = p + 2 \times i^2\]

Given \(k\) and a list of primes less than \(k\) the only remaining unknown is \(i\). Any solutions can be found by testing whether the following is a square for any prime \(p \lt k\):

\[\frac{k - p}{2}\]

Apply this search logic and return the first and thus lowest \(k\) without any such solutions.

Solution Implementation

from lib.numbertheory import is_square
from lib.sequence import Primes


def solve():
    """ Compute the answer to Project Euler's problem #46 """

    upper_bound = 10000  # found by trial and error

    primes = list(Primes(upper_bound=upper_bound))

    k = 3
    while k < upper_bound:
        while k in primes:
            k += 2  # ensure k is an odd composite

        # Search for a satisfying p,i s.t. k = p + 2 * i^2
        for prime in [prime for prime in primes if prime < k]:
            x = (k - prime) // 2
            if is_square(x):
                break
        else:
            return k

        k += 2


expected_answer = 5777

solutions.problem46.solve()

Compute the answer to Project Euler’s problem #46