Detailed mathematical approach

Problem Summary

We want the number of integers \(n\) with \(0 \le n \lt 50{,}000{,}000\) that can be written in the form

$n=p^2+q^3+r^4,$

where \(p\), \(q\), and \(r\) are prime. The important point is that we are counting distinct values of \(n\), not counting how many prime triples produce them.

So if two different choices of primes give the same sum, that integer should still be counted only once.

Mathematical Approach

The exponents \(2\), \(3\), and \(4\) make the search space much smaller than it first appears. Once those bounds are written down, the problem becomes a finite set-construction problem: build three short lists of prime powers, combine them in increasing order, and deduplicate the resulting sums.

Three finite prime-power sets

For a general limit \(N\), define

$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$

$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$

$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$

Then the required answer is

$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$

The exponent bounds are immediate:

$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$

Because \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\) for \(N>1\), a single sieve up to \(\sqrt{N}\) already produces every prime that can appear in any of the three lists.

Why direct enumeration is feasible

After the sieve, we are no longer searching through all integers below \(N\). We are combining one value from each of three finite sets. The square list is only moderately long, the cube list is much shorter, and the fourth-power list is tiny. That imbalance is exactly why a direct enumeration is practical for the Project Euler limit.

No recurrence or generating function is needed here. The real mathematical reduction is the observation that the problem is equivalent to taking a set sum of three bounded prime-power families.

Monotonicity and the early-break invariant

The primes are generated in increasing order, and the maps \(x\mapsto x^2\), \(x\mapsto x^3\), and \(x\mapsto x^4\) are strictly increasing on positive integers. Therefore each of the lists \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\), and \(\mathcal{S}_4(N)\) is already sorted.

This gives the key invariant behind the nested loops. Fix \(a\in\mathcal{S}_2(N)\). If \(a+b \ge N\) for some \(b\in\mathcal{S}_3(N)\), then every later cube \(b'\ge b\) also fails. Likewise, for fixed \(a\) and \(b\), if \(a+b+c \ge N\) for some \(c\in\mathcal{S}_4(N)\), then every later fourth power \(c'\ge c\) also fails.

So the search can stop at the first overflow inside each ordered loop. That is the decisive implementation invariant: once a partial sum reaches the limit, the remainder of that sorted suffix cannot contribute any valid value.

Distinct sums rather than distinct representations

The problem asks for representable integers, not for the number of representations. Mathematically, the object we want is the set

$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$

and the answer is simply \(|\mathcal{T}(N)|\).

That is why deduplication is essential. Even if different prime triples collide on the same sum, the set keeps only the underlying integer once.

Worked example: the small case \(N=50\)

For \(N=50\), the admissible prime powers are

$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$

Since there is only one fourth power below 50, every valid value has the form \(a+b+16\). Checking the possibilities gives

$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$

and every other choice is at least 50. Therefore

$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$

This miniature case already shows the complete strategy: form the three prime-power lists, enumerate their sums in increasing order, and count distinct valid totals.

How the Code Works

Prime generation and power construction

The C++, Python, and Java implementations first generate all primes up to \(\lfloor\sqrt{N}\rfloor+1\) with the Sieve of Eratosthenes. From that single ordered prime list they build three ordered arrays: prime squares below \(N\), prime cubes below \(N\), and prime fourth powers below \(N\).

The compiled implementations use 64-bit arithmetic while forming the powers so that the repeated multiplications remain safe even though every retained value is still below the final limit.

Nested loops with monotone cutoffs

After preprocessing, the implementation runs a triple nested enumeration over the square list, the cube list, and the fourth-power list. Because the lists are sorted, the moment a partial sum already reaches \(N\), the current loop stops immediately. This is the monotonicity argument from the mathematics section translated directly into code.

Hash-based deduplication

Every valid sum \(a+b+c \lt N\) is inserted into a hash-based set. If the same integer is produced again from a different triple of primes, the set keeps only one copy. The final output is the size of that set, which is exactly the number of distinct integers representable in the required form.

Complexity Analysis

Let \(B=\lfloor\sqrt{N}\rfloor\), and let \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\). The sieve phase costs \(O(B\log\log B)\) time and \(O(B)\) space.

The enumeration phase has worst-case time \(O(s_2s_3s_4)\), with average \(O(1)\) insertion into the deduplication set for each valid sum. In practice the work is smaller than the full product because the sorted lists allow early termination as soon as a partial sum reaches the limit.

Total space usage is \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\), dominated by the sieve table, the three prime-power lists, and the set of distinct sums. For \(N=50{,}000{,}000\), these structures remain small enough that the direct deduplicated enumeration is entirely practical.

Footnotes and References

1. Problem page: Project Euler 87
2. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
3. Prime number: Wikipedia - Prime number
4. Prime power: Wikipedia - Prime power
5. Set theory basics: Wikipedia - Set