Goldbach's other conjecture¶

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?

Idea¶

Naive solution.

Iterate through all odd numbers, split them into odd primes and odd composites.

For each odd composite, check if it can be wirtten as the format: $ odd = prime + 2 \times i^2, i \ is \ positive \ integer $. Notice, we do not need to check $prime = 2$

from math import sqrt

def is_prime(n):
    return all((n % d for d in range(3, int(sqrt(n))+1, 2)))

is_prime(3)

True

is_prime(9)

False

def solve():
    odd_primes = set()
    odd_composites = set()
    odd = 3
    while True:
        if is_prime(odd):
            odd_primes.add(odd)
        else:
            odd_composites.add(odd)
            
            square_i = range(1, int(sqrt(odd / 2))+1)
            squares = map(lambda i: pow(i, 2), square_i)
            remains = map(lambda sq: odd - 2*sq, squares)
            if all(map(lambda remain: remain not in odd_primes, remains)):
                return odd
        odd += 2

solve()

5777