Python Implementation of Problem 87
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 87
I ended up having to do this with recursion, which I normally do not like to use that much. Small changes can have large effects on later results. Still, this seems to work for the moment.
Revision 1:
Shorten the code slightly to take advantage of the primes() stop argument. Probably loses performance slightly.
Problem:
The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
28 = 2**2 + 2**3 + 2**4 33 = 3**2 + 2**3 + 2**4 49 = 5**2 + 2**3 + 2**4 47 = 2**2 + 3**3 + 2**4
How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
1"""
2Project Euler Problem 87
3
4I ended up having to do this with recursion, which I normally do not like to
5use that much. Small changes can have large effects on later results. Still,
6this seems to work for the moment.
7
8Revision 1:
9
10Shorten the code slightly to take advantage of the primes() stop argument.
11Probably loses performance slightly.
12
13Problem:
14
15The smallest number expressible as the sum of a prime square, prime cube, and
16prime fourth power is 28. In fact, there are exactly four numbers below fifty
17that can be expressed in such a way:
18
1928 = 2**2 + 2**3 + 2**4
2033 = 3**2 + 2**3 + 2**4
2149 = 5**2 + 2**3 + 2**4
2247 = 2**2 + 3**3 + 2**4
23
24How many numbers below fifty million can be expressed as the sum of a prime
25square, prime cube, and prime fourth power?
26"""
27from .lib.primes import primes
28
29
30def main() -> int:
31 seen = set()
32 root2_50M = int(50_000_000 ** (1/2)) + 1
33 root3_50M = int(50_000_000 ** (1/3)) + 1
34 root4_50M = int(50_000_000 ** (1/4)) + 1
35 for x in primes(root2_50M):
36 x2 = x * x
37 for y in primes(root3_50M):
38 y3 = y * y * y
39 for z in primes(root4_50M):
40 total = x2 + y3 + z * z * z * z
41 if total < 50_000_000:
42 seen.add(total)
43 else:
44 break
45 return len(seen)