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.