Detailed mathematical approach

Problem Summary

The required quantity is

$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$

Every summand begins from a positive triple

$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right), $

so initially \(C=A+B\). The crucial task is therefore not the outer double sum itself, but understanding how the function \(F(A,B,C)\) is determined for triples in which one coordinate equals the sum of the other two.

The three implementations all reveal the same structure. A triple is reduced by a subtraction-style Euclidean step, while we record which coordinate currently plays the role of the sum. Once that forward trace is known, the value of \(F\) is reconstructed backward by a simple rule modulo \(3\).

Mathematical Approach

Consider any positive triple \((A,B,C)\) satisfying exactly one of

$A=B+C,\qquad B=A+C,\qquad C=A+B.$

Because all entries are positive, the coordinate on the left-hand side is automatically the largest one. The reduction rule replaces that largest coordinate by the absolute difference of the other two.

The Reduction Preserves the Same Kind of State

If the current state satisfies \(C=A+B\), the next state is

$ (A,B,C)\mapsto (A,B,|A-B|). $

If \(A\ge B\), this becomes \((A,B,A-B)\), and then \(A=B+(A-B)\). If \(B>A\), it becomes \((A,B,B-A)\), and then \(B=A+(B-A)\). So after one step we still have a positive triple in which one coordinate is the sum of the other two; only the identity of that coordinate may change.

The same reasoning works cyclically in the other two cases. In other words, the process is a subtraction-based Euclidean algorithm applied to the two smaller numbers, with the coordinate labels \(A\), \(B\), and \(C\) remembering where the sum sits at each stage.

Invariants, Descent, and the Terminal Shapes

Two facts are immediate.

First, the common divisor is preserved. For example, when \(C=A+B\),

$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $

and the same identity holds in the other two cases after relabeling.

Second, as long as the two smaller numbers are different, the largest number strictly decreases. Hence the reduction must terminate.

Termination occurs exactly when the two smaller numbers become equal. If those equal values are \(g\), then the third coordinate must be \(2g\). Therefore the only terminal forms are

$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $

where \(g=\gcd(A,B,C)\). The scale \(g\) survives all the way to the end, but the implementations show that \(F\) depends only on which coordinate carries the factor \(2\), not on the actual magnitude of \(g\).

The Essential Object Is the Role Trace

During the forward reduction, record a symbol \(r_i\in\{A,B,C\}\) at each step to indicate which coordinate is currently equal to the sum of the other two. If the reduction ends after \(k\) steps, we obtain a trace

$ r_1,r_2,\dots,r_k, $

where \(r_k\) is also the role of the terminal form. Once this trace is known, the actual intermediate numbers are no longer needed for the second half of the computation.

The terminal states anchor the reconstruction through the base values

$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $

To propagate the answer backward through the trace, introduce the residue map

$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $

If the later state already has value \(t\) and the preceding role is \(r\), then the earlier state receives the smallest integer larger than \(t\) that lies in the required residue class:

$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $

Closed Form of the Backward Step

The minimization above can be written directly, so the backward pass needs no search:

$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $

This gives a compact recurrence for the whole function. The forward phase computes the role trace, the terminal role selects the starting value \(1\), \(2\), or \(3\), and the backward phase repeatedly applies the closed formula. That separation is the central idea of the solution.

Worked Example: The Summand with \((a,b)=(2,3)\)

Here

$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $

So we start from \((8,9,17)\), which already has role \(C\). The forward reduction is

$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $

The corresponding role trace is

$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $

The terminal state is of the form \((2g,g,g)\), so the starting value for backward reconstruction is \(1\). Now discard the last role \(A\), reverse the rest, and force the required residues \(2,1,2,1,2,1,2,0\):

$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $

Therefore

$ F(8,9,17)=12. $

This example comes directly from one term of the outer sum and shows both halves of the algorithm in action: forward Euclidean reduction, then backward residue reconstruction.

How the Code Works

Building the Input Triples

The C++, Python, and Java implementations iterate over all \(7\cdot 19=133\) pairs \((a,b)\). For each pair they compute \(A=a^b\), \(B=b^a\), form \(C=A+B\), evaluate \(F(A,B,C)\), and add the result to the running total.

The largest value that appears is still well within 64-bit range, so the implementations can stay entirely in integer arithmetic.

Forward Trace Generation

For one triple, the implementation repeatedly determines whether the current role is \(A\), \(B\), or \(C\), appends that role to a short list, and replaces the sum coordinate by the absolute difference of the remaining two values. The loop stops as soon as the two smaller numbers are equal, because the state has then reached one of the three terminal shapes.

Backward Reconstruction

After termination, the implementation converts the terminal role into the base value \(1\), \(2\), or \(3\). It then scans the stored trace backward, excluding the terminal role itself, and at each step jumps to the next larger integer in the residue class prescribed by that role. The closed formula above is exactly what the three implementations apply.

Complexity Analysis

Let \(L(A,B,C)\) denote the number of forward reduction steps for one triple. Computing that triple takes \(O(L(A,B,C))\) time: the forward pass is linear in the trace length, and the backward reconstruction is another linear pass over the same trace.

If the trace is stored explicitly, the auxiliary memory is \(O(L(A,B,C))\) for that triple. Since the full program evaluates only 133 triples, the total running time is

$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $

with working memory \(O(L_{\max})\) for the longest single trace. That is easily fast enough here because the outer search space is tiny and each inner step uses only comparisons, subtraction, and a modulo-\(3\) adjustment.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=905
2. Euclidean algorithm: Wikipedia - Euclidean algorithm
3. Greatest common divisor: Wikipedia - Greatest common divisor
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Absolute difference: Wikipedia - Absolute difference
6. Exponentiation: Wikipedia - Exponentiation