Problem 87: Prime Power Triples

Mathematical Analysis

Bounds on Primes

Given $n < 50{,}000{,}000$:

• $p^2 < 50{,}000{,}000 \Rightarrow p < 7072$, so we need primes up to 7071.
• $q^3 < 50{,}000{,}000 \Rightarrow q < 369$, so we need primes up to 368.
• $r^4 < 50{,}000{,}000 \Rightarrow r < 85$, so we need primes up to 84.

Editorial

The exponents immediately constrain the search space: fourth powers are the rarest and squares are the most common, so it is natural to precompute every prime power of each type that can possibly stay under the limit. After that, the problem becomes a bounded three-level enumeration.

The implementation loops over fourth powers first, then cubes, then squares. This order is useful because the partial sums grow quickly, so the inner loops can stop as soon as the current partial sum reaches the bound. Every valid sum is inserted into a set, which automatically filters out numbers that admit more than one representation. In other words, candidates are generated by combining admissible prime powers, and the global limit together with the set handles the pruning and deduplication.

Pseudocode

Generate all primes up to the largest bound needed for squares.
Create an empty set of reachable values.

For each prime fourth power below the limit:
    For each prime cube whose sum with that fourth power is still below the limit:
        For each prime square:
            Compute the total sum
            If the total reaches the limit, stop this square loop
            Insert the total into the set

Return the number of distinct values stored in the set.

Correctness

We enumerate all valid triples exhaustively. Using a set (or boolean array) ensures each expressible number is counted exactly once, regardless of how many representations it has.

Counting

The number of primes up to 7071 is approximately $7071 / \ln(7071) \approx 797$ (by the Prime Number Theorem). The number up to 368 is about 73, and up to 84 is about 23.

Total combinations to check: $\sim 797 \times 73 \times 23 \approx 1{,}338{,}569$, which is very manageable.

Complexity Analysis

• Time: $O(P_1 \cdot P_2 \cdot P_3)$ where $P_i$ are the counts of primes in each range. Approximately $O(1.3 \times 10^6)$.
• Space: $O(N)$ for the boolean array, where $N = 50{,}000{,}000$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int LIMIT = 50000000;

    // Sieve of Eratosthenes up to sqrt(LIMIT) for squares
    int sieve_limit = 7072;
    vector<bool> is_prime(sieve_limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= sieve_limit; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= sieve_limit; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    for (int i = 2; i <= sieve_limit; i++)
        if (is_prime[i]) primes.push_back(i);

    vector<bool> seen(LIMIT, false);
    int count = 0;

    for (int r : primes) {
        long long r4 = (long long)r * r * r * r;
        if (r4 >= LIMIT) break;
        for (int q : primes) {
            long long q3 = (long long)q * q * q;
            if (r4 + q3 >= LIMIT) break;
            for (int p : primes) {
                long long p2 = (long long)p * p;
                long long sum = r4 + q3 + p2;
                if (sum >= LIMIT) break;
                if (!seen[sum]) {
                    seen[sum] = true;
                    count++;
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

def solve():
    """
    Count numbers below 50,000,000 expressible as p^2 + q^3 + r^4
    where p, q, r are primes.
    """
    LIMIT = 50_000_000

    # Sieve of Eratosthenes
    sieve_limit = 7072
    is_prime = [True] * (sieve_limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(sieve_limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, sieve_limit + 1, i):
                is_prime[j] = False

    primes = [i for i in range(2, sieve_limit + 1) if is_prime[i]]

    seen = set()

    for r in primes:
        r4 = r ** 4
        if r4 >= LIMIT:
            break
        for q in primes:
            q3 = q ** 3
            if r4 + q3 >= LIMIT:
                break
            for p in primes:
                p2 = p ** 2
                s = r4 + q3 + p2
                if s >= LIMIT:
                    break
                seen.add(s)

    print(len(seen))

if __name__ == "__main__":
    solve()