Detailed mathematical approach

Problem Summary

The implementations ultimately evaluate the stabilized residue of the tower \(2, 2^2, 2^{2^2}, \dots\) modulo \(10^{15}\), and then report that residue shifted by \(3\):

$T(10^{15}) - 3 \pmod{10^{15}}.$

Here \(T(m)\) denotes the eventual residue of a sufficiently tall tower of 2s modulo \(m\). The main difficulty is that powers of 2 behave very differently on the odd part of the modulus and on its power-of-two part, so the computation separates those two pieces and handles them in different ways.

Mathematical Approach

Define the finite tower by \(a_1 = 2\) and \(a_{n+1} = 2^{a_n}\). For each modulus \(m\), the residues \(a_n \bmod m\) stabilize for large \(n\); call the stable residue \(T(m)\). The implementations compute \(T(m)\) by descending through the odd part of the modulus via Euler's totient function.

Step 1: Turn the tower into a modular fixed point

Once the residues stabilize, one more exponentiation produces the same class again, so the limit satisfies

$T(m) \equiv 2^{T(m)} \pmod{m}.$

This identity is not used as a brute-force equation solver. Its real purpose is to show that a very tall tower can be reconstructed from the behavior of its exponent modulo a smaller modulus.

Step 2: Split the modulus into a power of 2 and an odd part

Write

$m = 2^s q, \qquad q \text{ odd}.$

For a sufficiently tall tower, the outermost value is \(2^E\) with an exponent \(E\) much larger than \(s\), so the residue is automatically divisible by \(2^s\). Therefore

$T(m) \equiv 0 \pmod{2^s}.$

That means the residue can be written as

$T(m) \equiv 2^s u \pmod{m}$

for some class \(u \pmod{q}\). The problem is now reduced to finding this odd-part factor \(u\).

Step 3: Reduce the exponent modulo \(\varphi(q)\)

Because \(q\) is odd, \(\gcd(2,q)=1\), so Euler's theorem applies:

$2^{k+\varphi(q)} \equiv 2^k \pmod{q}.$

Thus the exponent only matters modulo \(\varphi(q)\). But that exponent is again a very tall tower of 2s, so its stable residue modulo \(\varphi(q)\) is exactly \(T(\varphi(q))\). Hence, modulo \(q\),

$T(m) \equiv 2^{T(\varphi(q))} \pmod{q}.$

Substituting \(T(m) \equiv 2^s u\) gives

$2^s u \equiv 2^{T(\varphi(q))} \pmod{q}.$

Step 4: Isolate the odd part and allow negative exponents

Since 2 is invertible modulo the odd number \(q\), we may divide by \(2^s\):

$u \equiv 2^{T(\varphi(q)) - s} \pmod{q}.$

If \(T(\varphi(q)) \ge s\), this is an ordinary modular power. If \(T(\varphi(q)) \lt s\), the exponent becomes negative, so we interpret it as

$2^{-r} \equiv (2^{-1})^r \pmod{q}.$

This is why the implementations explicitly compute the modular inverse of 2 on the odd modulus whenever the corrected exponent is negative.

Step 5: Reassemble the residue modulo \(m\)

Once \(u\) is known, the stabilized tower value is simply

$T(m) \equiv 2^s u \pmod{m}.$

For pure powers of two we have \(q=1\), so the answer is \(T(2^s)=0\). Otherwise the recursion continues with the strictly smaller modulus \(\varphi(q)\), which quickly reaches the base case

$T(1)=0.$

Worked Example: \(m = 40\)

Take \(m = 40 = 2^3 \cdot 5\). Then \(s=3\), \(q=5\), and

$\varphi(q) = \varphi(5) = 4.$

Because \(4\) is a power of two, a tall enough tower is divisible by \(4\), so

$T(4)=0.$

Therefore

$u \equiv 2^{T(4)-3} = 2^{-3} \pmod{5}.$

The inverse of \(2\) modulo \(5\) is \(3\), so

$u \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}.$

Hence

$T(40) \equiv 2^3 \cdot 2 = 16 \pmod{40}.$

A direct check confirms the fixed-point relation:

$2^{16} = 65536 \equiv 16 \pmod{40}.$

How the Code Works

The C++, Python, and Java implementations all follow the same recursion. They memoize the stabilized residue for each modulus appearing on the totient chain, starting from the base value \(T(1)=0\). For the current modulus they remove all factors of 2, compute the odd part \(q\), factor \(q\) to obtain \(\varphi(q)\), recurse to find \(T(\varphi(q))\), and then correct the exponent by subtracting the number of removed factors of 2.

The odd-part contribution is evaluated as a modular power of 2. When the corrected exponent is negative, the implementation first finds the modular inverse of 2 modulo \(q\) with the extended Euclidean algorithm and then raises that inverse to the needed positive power. Finally it restores the factor \(2^s\), reduces modulo the original modulus, and after the top-level call at \(10^{15}\) it subtracts \(3\) modulo \(10^{15}\).

Complexity Analysis

Let \(m_0 = m\), and at level \(i\) write \(m_i = 2^{s_i} q_i\) with \(q_i\) odd. The recursion then moves to \(m_{i+1} = \varphi(q_i)\) until it reaches 1. The depth is the length of this chain. At each level, the direct implementation computes \(\varphi(q_i)\) by trial division up to \(\sqrt{q_i}\), and performs one modular exponentiation costing \(O(\log q_i)\) modular multiplications. Therefore the running time is

$O\left(\sum_i \sqrt{q_i} + \sum_i \log q_i\right),$

while the memo table stores one residue per chain value, so the memory use is \(O(k)\), where \(k\) is the chain length. For the actual target modulus the chain shrinks very quickly, so the practical runtime is small.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=809
2. Euler's totient function: Wikipedia - Euler's totient function
3. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse
4. Tetration and infinite power towers: Wikipedia - Tetration
5. Chinese remainder theorem: Wikipedia - Chinese remainder theorem