## Project Euler Problem 87 Solution

## Question

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?

## Python

```
#!/usr/bin/env python
from itertools import product, takewhile
def euler(n):
# Create a candidate list within which non-primes will
# marked as None, noting that only candidates below
# sqrt(n) need be checked.
candidates = list(range(n+1))
fin = int(n**0.5)
# Loop over the candidates, marking out each multiple.
# If the current candidate is already checked off then
# continue to the next iteration.
for i in range(2, fin+1):
if not candidates[i]:
continue
candidates[2*i::i] = [None] * (n//i - 1)
# Filter out non-primes and return the list.
return [i for i in candidates[2:] if i]
def main():
limit = 50000000
primes = euler(int(limit**0.5))
squares = takewhile(lambda x: x < limit, (prime**2 for prime in primes))
cubes = takewhile(lambda x: x < limit, (prime**3 for prime in primes))
tesseracts = takewhile(lambda x: x < limit, (prime**4 for prime in primes))
print((len(set(s + c + t for (s, c, t) in product(squares, cubes, tesseracts) if s + c + t < limit))))
if __name__ == "__main__": main()
```

```
$ time python3 triples.py
real 0m0.495s
user 0m0.460s
sys 0m0.032s
```

Questions? Comments? Send me an email: [email protected]