Python Implementation of Problem 46
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 46
Didn't even need to rearrange the formula to solve it trivially
Revision 1:
It turns out that rearranging the formula let me cut the time by ~50x
Problem:
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?
1"""
2Project Euler Problem 46
3
4Didn't even need to rearrange the formula to solve it trivially
5
6Revision 1:
7
8It turns out that rearranging the formula let me cut the time by ~50x
9
10Problem:
11
12It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a
13square.
14
159 = 7 + 2×1^2
1615 = 7 + 2×2^2
1721 = 3 + 2×3^2
1825 = 7 + 2×3^2
1927 = 19 + 2×2^2
2033 = 31 + 2×1^2
21
22It turns out that the conjecture was false.
23
24What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
25"""
26from itertools import count, takewhile
27from math import ceil, sqrt
28
29from .lib.primes import is_prime, primes
30
31
32def main() -> int:
33 cached_primes = tuple(primes(6000))
34 for goal in count(35, 2):
35 if is_prime(goal):
36 continue
37 for p in takewhile(goal.__gt__, cached_primes):
38 done = False
39 for x in range(1, ceil(sqrt((goal - p) / 2)) + 1):
40 if p + 2 * x * x == goal:
41 done = True
42 break
43 if done:
44 break
45 else:
46 return goal
47 return -1 # pragma: no cover