Detailed mathematical approach

Problem Summary

Problem 188 asks for the last eight digits of the tetration

$1777 \uparrow\uparrow 1855 = 1777^{1777^{.^{.^{1777}}}}$

where the exponent tower has height \(1855\). Writing down the exponent is hopeless: even the third level is already astronomically large. The task is therefore not to evaluate the tower itself, but to compute its residue modulo \(10^8\).

Mathematical Approach

The implementations solve the problem by replacing one enormous exponent tower with a short chain of smaller modular subproblems. The crucial tool is Euler's theorem, but for this specific input the modulus \(10^8\) has such a simple prime-power structure that the entire reduction can be written very explicitly.

Tetration as a recursive residue problem

Let

$T_h = 1777 \uparrow\uparrow h,$

and let \(R(h,m)\) denote \(T_h \bmod m\). Then

$R(1,m)=1777 \bmod m,$

and for \(h \ge 2\),

$T_h = 1777^{T_{h-1}}.$

If \(\gcd(1777,m)=1\), Euler's theorem gives

$1777^x \equiv 1777^{\,x \bmod \varphi(m)} \pmod m,$

so only the exponent modulo \(\varphi(m)\) is needed. That turns the tower into the recurrence

$R(h,m)=1777^{\,R(h-1,\varphi(m))} \bmod m,$

provided the modulus at that level is coprime to \(1777\). This is the core recurrence used by all three implementations.

The totient chain for \(10^8\)

The modulus is

$10^8 = 2^8 \cdot 5^8.$

For numbers of the form \(2^a5^b\) with \(a,b \ge 1\), Euler's totient function is

$\varphi(2^a5^b)=2^a5^b\left(1-\frac12\right)\left(1-\frac15\right)=2^{a+1}5^{b-1}.$

Starting from \(10^8\), repeated totients therefore give the explicit chain

$100000000 \to 40000000 \to 16000000 \to 6400000 \to 2560000 \to 1024000 \to 409600 \to 163840 \to 65536 \to 32768 \to \cdots \to 1.$

Two facts matter here. First, after eight totients the factor \(5^b\) disappears and only powers of \(2\) remain. Second, after only 24 totient steps the modulus has already fallen to \(1\). So a tower of height \(1855\) does not create \(1855\) genuinely different subproblems; only the first 25 modulus levels matter.

Why Euler reduction is exact for this problem

The base \(1777\) is divisible by neither \(2\) nor \(5\). Every modulus in the chain above is of the form \(2^a5^b\), so

$\gcd(1777,m_i)=1$

for every modulus \(m_i\) that appears during the recursion. That means the clean coprime recurrence applies at every level of the actual Project Euler input:

$R(1855,10^8)=1777^{\,R(1854,40000000)} \bmod 10^8,$

$R(1854,40000000)=1777^{\,R(1853,16000000)} \bmod 40000000,$

and so on, until the modulus becomes \(1\), at which point the recursive value is automatically \(0\). The algorithm never needs the full exponent \(T_{h-1}\); it only needs its residue modulo the next totient.

Worked example: \(3 \uparrow\uparrow 3 \bmod 100\)

The checkpoint used by the implementations is small enough to show the mechanism completely. Since

$100 \to \varphi(100)=40 \to \varphi(40)=16,$

we compute from the top of the chain downward:

$3 \uparrow\uparrow 1 \equiv 3 \pmod{16},$

$3 \uparrow\uparrow 2 = 3^3 \equiv 27 \pmod{40},$

$3 \uparrow\uparrow 3 = 3^{27} \equiv 87 \pmod{100}.$

This is exactly the same recursion as the real problem, just with much smaller numbers. The large Euler 188 tower is solved by repeating the same descent along the totient chain of \(10^8\).

How the Code Works

Number-theoretic building blocks

The implementation first needs two standard primitives. One computes \(\varphi(m)\) by factoring the current modulus with trial division and applying the product formula for Euler's totient. The other computes \(a^e \bmod m\) by binary modular exponentiation, so the cost grows only logarithmically with the exponent size instead of linearly.

Recursive evaluation of the tower

The C++, Python, and Java implementations then evaluate the tetration residue recursively. If the modulus is \(1\), the residue is immediately \(0\). If the height is \(1\), the result is simply \(1777 \bmod m\). Otherwise the code descends once to modulus \(\varphi(m)\), obtains the smaller residue needed for the exponent, and raises \(1777\) to that exponent modulo the current modulus.

The implementations also include a standard safeguard for non-coprime cases: after the recursive call, they add one totient period before modular exponentiation whenever the base and modulus are not coprime. That branch makes the routine more generally usable, but for Problem 188 it never fires, because every modulus encountered is still coprime to \(1777\).

Language-specific execution details

The three versions differ only in low-level mechanics. The Python implementation uses the language's built-in modular power with an explicit modulus argument. The Java implementation delegates modular exponentiation to its arbitrary-precision integer library. The C++ implementation performs modular multiplication in a wider integer type before reducing modulo \(m\), which keeps the routine safe even if larger inputs are supplied from the command line. Mathematically, however, all three versions execute the same totient-chain recursion.

Complexity Analysis

If \(m_0=10^8\) and \(m_{i+1}=\varphi(m_i)\), let \(L\) be the first index with \(m_L=1\). For this problem, \(L=24\), so the recursion has only about two dozen meaningful levels, not \(1855\). Memory usage is therefore \(O(L)\), which is tiny in practice.

At level \(i\), the code factors \(m_i\) by trial division to obtain \(\varphi(m_i)\), then performs one modular exponentiation whose cost is \(O(\log m_i)\) modular multiplications because the exponent is already reduced modulo \(m_{i+1}\). A clean way to summarize the running time is

$O\!\left(\sum_{i=0}^{L-1}\bigl(\sqrt{m_i}+\log m_i\bigr)\right).$

Since the moduli collapse rapidly from \(10^8\) to \(1\), this is easily fast enough for the given input.

Footnotes and References

1. Project Euler Problem 188: https://projecteuler.net/problem=188
2. Tetration: Wikipedia - Tetration
3. Euler's theorem: Wikipedia - Euler's theorem
4. Euler's totient function: Wikipedia - Euler's totient function
5. Modular exponentiation: Wikipedia - Modular exponentiation