Project Euler Problem 046

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.

$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?

Solution

Brute-force approach.

from CommonFunctions import find_primes_less_than
 
def has_property(n):
    index = 0
    while index < len(lst_two_squares) and lst_two_squares[index] < n:
        if (n - lst_two_squares[index]) in primes:
            return True
        index += 1
    return False
 
primes = set(find_primes_less_than(30000))
lst_two_squares = [2 * (i ** 2) for i in range(1,2000)]
 
if __name__ == '__main__':
    result = 9
    while has_property(result):
        result += 2
        while result in primes:
            result += 2
    print("The result is:", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License