Detailed mathematical approach

Problem Summary

Let \(F(n)\) be the number of tuples \((a,b,c,e,f)\) of positive integers satisfying

$a^e+b^e=c^f\le n,\qquad a<b,\qquad e\ge 2,\qquad f\ge 3.$

The goal is to compute \(F(10^{18})\). The challenge is that the same right-hand side value can be a perfect power in more than one way, while the left-hand side behaves very differently for \(e=2\), \(e=3\), and \(e\ge 4\).

Mathematical Approach

The implementation separates the problem into three parts. First it catalogs all perfect powers \(c^f\le n\) with \(f\ge 3\). Then it counts representations \(a^e+b^e=N\) using a special method for squares, another for cubes, and a direct scan for higher exponents.

Step 1: Catalog Every Perfect Power on the Right-Hand Side

For every base \(c\ge 2\) and exponent \(f\ge 3\), generate

$N=c^f\le n.$

This produces a catalogue of perfect-power descriptions, not merely a set of distinct values. That distinction matters because one numerical value may support several exponents. If a number is both a cube and a fifth power, then a single identity \(a^e+b^e=N\) contributes once for each admissible exponent \(f\).

For each numerical value \(N\), the implementation stores the full set of exponents \(f\) with \(N=c^f\). The largest possible exponent is

$f_{\max}=\left\lfloor \log_2 n \right\rfloor,$

because \(2^f\le n\) is the smallest perfect power having exponent \(f\).

Step 2: Treat \(e=2\) with the Sum-of-Two-Squares Theorem

Fix a perfect power \(N=c^f\), and write

$N=\prod p^{\alpha_p}.$

The classical formula for the number of integer solutions of \(x^2+y^2=N\) is

$r_2(N)=4\prod_{p\equiv 1 \pmod 4}(\alpha_p+1),$

provided every prime \(p\equiv 3\pmod 4\) appears with even exponent. If one such prime has odd exponent, then \(r_2(N)=0\).

This count includes signs and order, so it is not yet the desired number of positive pairs with \(a<b\). Two special families must be removed first:

$\text{axis solutions }(t,0)\text{ or }(0,t),\qquad \text{equal solutions }(t,t).$

If \(N\) is a square, there are four axis solutions. If \(N=2t^2\), there are four equal solutions. Every remaining nonzero unequal representation occurs in exactly \(8\) signed-and-ordered forms, so the required count is

$\frac{r_2(N)-\text{axis}-\text{equal}}{8}.$

Because \(N=c^f\), it is enough to factor \(c\) and multiply every prime exponent by \(f\).

Step 3: Treat \(e=3\) by Factoring \(a^3+b^3\)

For cubes we use the identity

$a^3+b^3=(a+b)(a^2-ab+b^2).$

Set

$u=a+b,\qquad v=a^2-ab+b^2,\qquad N=uv.$

Now enumerate divisors \(u\mid N\), set \(v=N/u\), and recover \(a\) and \(b\) from symmetric data. Since

$u^2-v=3ab,$

we obtain

$ab=\frac{u^2-v}{3}.$

Then \(a\) and \(b\) are roots of

$t^2-ut+ab=0,$

so the discriminant

$\Delta=u^2-4ab$

must be a perfect square. If \(\Delta=s^2\) and \(u\pm s\) are even, then

$a=\frac{u-s}{2},\qquad b=\frac{u+s}{2}.$

Only solutions with \(a>0\) and \(a<b\) are kept. The implementation also skips right-hand-side exponents divisible by \(3\), because then \(c^f\) is itself a cube and \(a^3+b^3=z^3\) would contradict Fermat's Last Theorem for positive integers.

Step 4: Scan Directly for \(e\ge 4\)

For a fixed exponent \(e\ge 4\), precompute

$1^e,2^e,\dots,\left\lfloor n^{1/e}\right\rfloor^e.$

For each \(b\), admissible values of \(a\) satisfy

$1\le a\le \min\!\left(b-1,\left\lfloor (n-b^e)^{1/e}\right\rfloor\right).$

Each candidate sum

$s=a^e+b^e$

is looked up in the perfect-power catalogue. If \(s=c^f\) for several exponents \(f\), each such exponent contributes except the multiples of \(e\). Indeed, if \(e\mid f\), then

$s=c^f=\left(c^{f/e}\right)^e,$

which would produce a nontrivial solution of \(a^e+b^e=z^e\), impossible for \(e\ge 3\).

There is also a parity pruning for even \(e\). If both \(a\) and \(b\) are odd, then

$a^e+b^e\equiv 1+1\equiv 2 \pmod 4,$

but a perfect power \(c^f\) with \(f\ge 3\) is either odd or divisible by \(8\), never \(2\bmod 4\). So when \(e\) is even and \(b\) is odd, only even values of \(a\) need to be tested.

Step 5: Why Duplicate Perfect-Power Values Still Matter

The count is over exponent choices as well as numerical values. A single value \(N\) may correspond to several admissible right-hand-side exponents, so a solution \(a^e+b^e=N\) may contribute more than once. This is why the implementation keeps both a list of all perfect-power descriptions and a compact record of which exponents belong to each value.

Worked Example: \(n=1000\)

The checkpoint built into the implementation is

$F(1000)=7.$

The seven counted tuples come from exactly four right-hand-side values:

$125=2^2+11^2=5^2+10^2=5^3,$

$243=3^3+6^3=3^5,$

$625=7^2+24^2=15^2+20^2=5^4,$

$1000=10^2+30^2=18^2+26^2=10^3.$

That is \(2+1+2+2=7\). The square cases are detected by the two-squares theorem, the cubic case is reconstructed from divisors and a discriminant test, and no exponent \(e\ge 4\) contributes below \(1000\).

How the Code Works

The C++, Python, and Java implementations all follow the same counting strategy. They first enumerate all perfect powers \(c^f\le 10^{18}\) with \(f\ge 3\), preserving every individual \((c,f)\) description while also recording, for each value \(N\), the set of exponents that produce it.

Next, the implementation builds a smallest-prime-factor sieve up to the largest base appearing in the catalogue. The \(e=2\) branch uses that sieve to factor bases quickly and then applies the sum-of-two-squares theorem. The \(e=3\) branch enumerates divisors of the perfect power, reconstructs possible pairs \((a,b)\), and caches the cubic count for each numerical value so repeated values are not recomputed.

For \(e\ge 4\), the implementation precomputes the table of \(e\)-th powers, scans the admissible range \(a<b\), applies the parity pruning for even exponents, and consults the perfect-power catalogue for every sum. The C++ implementation parallelizes large outer loops; the Python implementation keeps the same logic in a direct serial form; the Java implementation delegates to the same computational core.

Complexity Analysis

Let

$M=\sum_{f=3}^{\lfloor \log_2 n\rfloor}\left\lfloor n^{1/f}\right\rfloor.$

Generating the perfect-power catalogue costs \(O(M)\), dominated by cubes and therefore behaving like \(O(n^{1/3})\). Building the smallest-prime-factor sieve up to the largest base costs \(O(n^{1/3}\log\log n)\) time and \(O(n^{1/3})\) memory.

The \(e=2\) branch is essentially linear in the number of catalogue entries after sieve preprocessing. The \(e=3\) branch depends on divisor enumeration for the perfect powers that survive the \(3\nmid f\) filter, but caching makes repeated values cheap. The dominant direct scan is

$\sum_{e=4}^{\lfloor \log_2 n\rfloor} O\!\left(n^{2/e}\right),$

with the largest contribution coming from \(e=4\). In practice, the special handling of \(e=2\) and \(e=3\), parity pruning, perfect-power lookup, and parallel work splitting make the full \(n=10^{18}\) computation feasible.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=678
2. Perfect power: Wikipedia - Perfect power
3. Fermat's theorem on sums of two squares: Wikipedia - Fermat's theorem on sums of two squares
4. Sum of two cubes: Wikipedia - Sum of two cubes
5. Fermat's Last Theorem: Wikipedia - Fermat's Last Theorem