Project Euler Solution 46: Goldbach's other conjecture

Problem 46: Goldbach's other conjecture is about non-prime numbers that can be written as the sum of a prime and twice a square number.

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?

First I had to look up what a composite number is. It is just a number that is the product of two numbers, so essentially it is neither 1 nor a prime number.

Assuming that the number to be found is rather small, we can use a sieve approach again. We take all primes and then take all possible squares that in sum don't exceed a predetermined ceiling. In order to get the primes, we use the prime sieve from Solution 7: 10001st prime. Then we can check off the numbers that we can reach. The first odd composite number that did not reach in the first step is the one that we wanted to find.

def solution() -> int:
    ceiling = 10_000
    conjecture_holds = [False] * ceiling
    conjecture_holds[0] = True
    conjecture_holds[1] = True
    primes = prime_sieve(ceiling)
    for prime in primes:
        conjecture_holds[prime] = True
        for i in range(1, int(math.sqrt((ceiling - prime) / 2)) + 1):
            number = prime + 2 * i**2
            if number < ceiling:
                conjecture_holds[number] = True
    for number, holds in enumerate(conjecture_holds):
        if not holds and number % 2 == 1:
            return number

This runs in 8.4 ms, so I am quite satisfied with that solution.