Euler – Coder.si

Prime power triples

Problem 87

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?

from tools import primes_first_908

def run(limit=50000000):
    num = {}
    count = 0

    for i in range(len(primes_first_908)):
        p1 = primes_first_908[i]
        to4 = p1*p1*p1*p1
        if to4 > limit - 24:
            break

        for j in range(len(primes_first_908)):
            p2 = primes_first_908[j]
            to3 = p2*p2*p2
            if to4 + to3 > limit:
                break

            for k in range(len(primes_first_908)):
                p3 = primes_first_908[k]
                to2 = p3*p3
                if to4 + to3 + to2 > limit:
                    break

                n = to4 + to3 + to2
                if not num.get(n):
                    count += 1
                    num[n] = 1

    return count