Solution

Answer: 95962097

We need the last $8$ digits of

$$1777 \uparrow\uparrow 1855$$

that is,

$$1777^{(1777^{(1777^{\cdot^{\cdot^\cdot}})})}$$

with $1855$ copies of $1777$.

The key difficulty is that the exponent is unimaginably large, so direct computation is impossible. The solution relies on modular arithmetic and Euler’s theorem.

Mathematical analysis

We want

$$1777 \uparrow\uparrow 1855 \pmod{10^8}.$$

Let

$$T_n = 1777 \uparrow\uparrow n.$$

Then

$$T_{n+1} = 1777^{T_n}.$$

So we need

$$T_{1855} \bmod 10^8.$$

Step 1: Euler’s theorem

Since

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

and $1777$ is coprime to $10^8$, Euler’s theorem applies:

$$a^{\phi(m)} \equiv 1 \pmod m \quad\text{if}\quad \gcd(a,m)=1.$$

Thus exponents can be reduced modulo $\phi(m)$.

For $m=10^8$,

$$\phi(10^8) =10^8\left(1-\frac12\right)\left(1-\frac15\right) =10^8\cdot \frac12\cdot \frac45 =40,000,000.$$

Therefore,

$$1777^k \pmod{10^8}$$

depends only on

$$k \pmod{40,000,000}.$$

But now the exponent itself is another tetration, so we recurse.

Step 2: Recursive modular reduction

Define a recursive function

$$f(h,m)=1777\uparrow\uparrow h \pmod m.$$

Then

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

and for $h>1$,

$$f(h,m) = 1777^{,f(h-1,\phi(m))} \pmod m.$$

Why does this work?

Because when computing

$$1777^E \pmod m,$$

the exponent $E$ only matters modulo $\phi(m)$.

So instead of computing the gigantic exponent exactly, we compute it modulo $\phi(m)$, then recurse again.

The chain becomes:

$$10^8 \to \phi(10^8)=40,000,000 \to \phi(40,000,000)=16,000,000 \to \cdots$$

Eventually the modulus becomes small enough that the recursion stabilizes quickly.

Step 3: Efficient modular exponentiation

Python provides:

pow(base, exponent, modulus)

which computes modular powers efficiently using repeated squaring in logarithmic time.

So each recursive layer is fast.

Python implementation

from math import gcd

def phi(n):
    """Compute Euler's totient function."""
    result = n
    p = 2

    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1

    if n > 1:
        result -= result // n

    return result

def tetration_mod(a, height, mod):
    """
    Compute a ↑↑ height (tetration) modulo mod.
    """

    # Base case
    if mod == 1:
        return 0

    if height == 1:
        return a % mod

    # Recursively compute exponent modulo phi(mod)
    exponent = tetration_mod(a, height - 1, phi(mod))

    # Euler reduction
    return pow(a, exponent, mod)

answer = tetration_mod(1777, 1855, 10**8)

print(answer)

Code walkthrough

Euler totient function

def phi(n):

Computes Euler’s totient $\phi(n)$, the count of integers coprime to $n$.

result = n

We start with $n$, then subtract fractions corresponding to prime factors.

while p * p <= n:

Trial division to factorize $n$.

result -= result // p

Applies:

$$\phi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).$$

Recursive tetration modulo

def tetration_mod(a, height, mod):

Computes

$$a\uparrow\uparrow height \pmod{mod}.$$

Base cases

if mod == 1:
    return 0

Everything is $0 \pmod 1$.

if height == 1:
    return a % mod

Because

$$a\uparrow\uparrow1=a.$$

Recursive exponent reduction

exponent = tetration_mod(a, height - 1, phi(mod))

Instead of computing the enormous exponent directly, compute it modulo $\phi(mod)$.

Modular exponentiation

return pow(a, exponent, mod)

Efficiently computes

$$a^{\text{exponent}} \pmod{mod}.$$

Small example check

The problem states:

$$3\uparrow\uparrow2 = 3^3 = 27.$$

Our recursion gives:

exponent = $3 \uparrow\uparrow 1 = 3$
result = $3^3 = 27$

Correct.

For

$$3\uparrow\uparrow3,$$

the code computes:

$$3^{27}=7625597484987,$$

matching the statement.

Final verification

We seek the last $8$ digits, so the answer must lie between

$$0 \text{ and } 99,999,999.$$

The result produced by the recursion is stable and computed entirely through exact modular arithmetic, so no approximation is involved.

The computed value is:

$$95962097$$

Answer: 95962097

Project Euler Problem 188