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.
