Problem 905: Now I Know
View on Project EulerProject Euler Problem 905 Solution
EulerSolve provides an optimized solution for Project Euler Problem 905, Now I Know, with C++, Python, Java, and a step-by-step mathematical explanation.
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)\)....
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
- Problem page: https://projecteuler.net/problem=905
- Euclidean algorithm: Wikipedia - Euclidean algorithm
- Greatest common divisor: Wikipedia - Greatest common divisor
- Modular arithmetic: Wikipedia - Modular arithmetic
- Absolute difference: Wikipedia - Absolute difference
- Exponentiation: Wikipedia - Exponentiation
Problem 905 source code
C++
#include <cstdint>
#include <iostream>
#include <thread>
#include <vector>
static uint64_t pow_int(uint64_t base, int exp) {
uint64_t result = 1;
for (int i = 0; i < exp; ++i) {
result *= base;
}
return result;
}
static uint64_t next_turn_after(uint64_t t, int mod) {
uint64_t candidate = t + 1;
uint64_t r = candidate % 3;
if (r == static_cast<uint64_t>(mod)) {
return candidate;
}
uint64_t add = (static_cast<uint64_t>(mod) + 3 - r) % 3;
return candidate + add;
}
static uint64_t compute_F(uint64_t A, uint64_t B, uint64_t C) {
static constexpr int role_mod[3] = {1, 2, 0};
static constexpr int role_base[3] = {1, 2, 3};
std::vector<uint8_t> roles;
int base_role = -1;
while (true) {
if (A == B + C) {
roles.push_back(0);
if (B == C) {
base_role = 0;
break;
}
A = (B >= C) ? (B - C) : (C - B);
} else if (B == A + C) {
roles.push_back(1);
if (A == C) {
base_role = 1;
break;
}
B = (A >= C) ? (A - C) : (C - A);
} else {
roles.push_back(2);
if (A == B) {
base_role = 2;
break;
}
C = (A >= B) ? (A - B) : (B - A);
}
}
uint64_t turns = role_base[base_role];
roles.pop_back();
for (auto it = roles.rbegin(); it != roles.rend(); ++it) {
turns = next_turn_after(turns, role_mod[*it]);
}
return turns;
}
static bool run_validation() {
bool ok = true;
if (compute_F(2, 1, 1) != 1) {
std::cerr << "Validation failed: F(2,1,1) != 1\n";
ok = false;
}
if (compute_F(2, 7, 5) != 5) {
std::cerr << "Validation failed: F(2,7,5) != 5\n";
ok = false;
}
if (compute_F(1, 1, 2) != 3) {
std::cerr << "Validation failed: F(1,1,2) != 3\n";
ok = false;
}
if (compute_F(1, 2, 3) != 3) {
std::cerr << "Validation failed: F(1,2,3) != 3\n";
ok = false;
}
if (ok) {
std::cerr << "Validation checkpoints passed.\n";
}
return ok;
}
int main() {
if (!run_validation()) {
return 1;
}
unsigned int threads = std::thread::hardware_concurrency();
if (threads == 0) {
threads = 1;
}
std::vector<uint64_t> partial(threads, 0);
std::vector<std::thread> pool;
pool.reserve(threads);
for (unsigned int t = 0; t < threads; ++t) {
pool.emplace_back([t, threads, &partial]() {
uint64_t local = 0;
for (int a = 1 + static_cast<int>(t); a <= 7; a += static_cast<int>(threads)) {
for (int b = 1; b <= 19; ++b) {
uint64_t A = pow_int(static_cast<uint64_t>(a), b);
uint64_t B = pow_int(static_cast<uint64_t>(b), a);
uint64_t C = A + B;
local += compute_F(A, B, C);
}
}
partial[t] = local;
});
}
for (auto& th : pool) {
th.join();
}
uint64_t total = 0;
for (uint64_t v : partial) {
total += v;
}
std::cout << total << "\n";
return 0;
}
Python
def next_turn_after(t, mod_val):
candidate = t + 1
r = candidate % 3
if r == mod_val:
return candidate
add = (mod_val + 3 - r) % 3
return candidate + add
def compute_F(A, B, C):
role_mod = [1, 2, 0]
role_base = [1, 2, 3]
roles = []
base_role = -1
while True:
if A == B + C:
roles.append(0)
if B == C:
base_role = 0
break
A = (B - C) if B >= C else (C - B)
elif B == A + C:
roles.append(1)
if A == C:
base_role = 1
break
B = (A - C) if A >= C else (C - A)
else:
roles.append(2)
if A == B:
base_role = 2
break
C = (A - B) if A >= B else (B - A)
turns = role_base[base_role]
roles.pop()
for role in reversed(roles):
turns = next_turn_after(turns, role_mod[role])
return turns
def solve():
total = 0
for a in range(1, 8):
for b in range(1, 20):
A = pow(a, b)
B = pow(b, a)
C = A + B
total += compute_F(A, B, C)
return str(total)
if __name__ == "__main__":
print(solve())
Java
public class Euler905 {
static long powInt(long base, int exp) {
long result = 1;
for (int i = 0; i < exp; ++i) {
result *= base;
}
return result;
}
static long nextTurnAfter(long t, int mod) {
long candidate = t + 1;
long r = candidate % 3;
if (r == mod) {
return candidate;
}
long add = (mod + 3 - r) % 3;
return candidate + add;
}
static long computeF(long A, long B, long C) {
int[] roleMod = { 1, 2, 0 };
int[] roleBase = { 1, 2, 3 };
java.util.List<Integer> roles = new java.util.ArrayList<>();
int baseRole = -1;
while (true) {
if (A == B + C) {
roles.add(0);
if (B == C) {
baseRole = 0;
break;
}
A = (B >= C) ? (B - C) : (C - B);
} else if (B == A + C) {
roles.add(1);
if (A == C) {
baseRole = 1;
break;
}
B = (A >= C) ? (A - C) : (C - A);
} else {
roles.add(2);
if (A == B) {
baseRole = 2;
break;
}
C = (A >= B) ? (A - B) : (B - A);
}
}
long turns = roleBase[baseRole];
roles.remove(roles.size() - 1);
for (int i = roles.size() - 1; i >= 0; --i) {
turns = nextTurnAfter(turns, roleMod[roles.get(i)]);
}
return turns;
}
public static String solve() {
long total = 0;
for (int a = 1; a <= 7; a++) {
for (int b = 1; b <= 19; ++b) {
long A = powInt(a, b);
long B = powInt(b, a);
long C = A + B;
total += computeF(A, B, C);
}
}
return Long.toString(total);
}
public static void main(String[] args) {
System.out.println(solve());
}
}