Problem Description

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?

Analysis

This is a problem that brute force solves so quickly and easily that much more investigation is hardly warranted. It’s not obvious that any other approach would produce a much faster solution.

Basically, this routine generates three lists of prime numbers: one each for the square root, cube root and fourth root of the limit. Then we iterate over the lists and calculate unique numbers below 50,000,000 as p₂² + p₃³ + p₄⁴, where p₂, p₃,and p₄ are prime numbers from each list (they are not nesessarily unique from one another.)
Placing the results in a set prevents duplicates from being counted. The length of the set is the how many numbers fit the criteria.

Solution

Runs < 2 seconds in Python.

from Euler import prime_sieve
 
limit = 50000000
P=set()
p2_list = prime_sieve(7072)
p3_list = prime_sieve(369)
 
for p4 in prime_sieve(84):
  for p3 in p3_list: 
    qz =  p3**3 + p4**4
    if qz>=limit: break
    for p2 in p2_list:
      z = p2**2 + qz
      if z>=limit: break
      P.add(z)
 
print "Answer to PE87 =",len(P)

Comments

Runs for 1,409,343 iterations.