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⁴
33 = 3² + 2³ + 2⁴
49 = 5² + 2³ + 2⁴
47 = 2² + 3³ + 2⁴

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.489s
user   0m0.457s
sys    0m0.032s