Problem 188: The Hyperexponentiation of a Number

Project Euler Problem 188 Solution

EulerSolve provides an optimized solution for Project Euler Problem 188, The Hyperexponentiation of a Number, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

The tetration, or hyperexponentiation, of a number $a$ by a positive integer $b$, written $a\uparrow\uparrow b$ or ${}^ba$, is defined by $a\uparrow\uparrow1=a$ and $a\uparrow\uparrow(k+1)=a^{a\uparrow\uparrow k}$: a tower of $b$ copies of $a$. The statement gives $3\uparrow\uparrow2=3^3=27$ and $3\uparrow\uparrow3=3^{27}=7625597484987$, says that $3\uparrow\uparrow4$ is roughly $10^{3.6383346400240996\cdot10^{12}}$, and asks for the last $8$ digits of $1777\uparrow\uparrow1855$, that is, for its remainder after division by $10^8$. ^[1]

The whole solution in one sentence: since $10^8$ and every smaller modulus met on the way are coprime to $1777$, Euler's theorem lets us replace each enormous exponent by its remainder modulo a smaller modulus, $\varphi(m)$ instead of $m$, and after $24$ such steps the modulus is $1$, so that $24$ small modular powers, evaluated on the way back up, give the result.

Mathematical Approach

We first see why the tower cannot be written down, then how the remainders of powers repeat, and finally turn this into a descent of $24$ short steps.

1. A tower too tall to write down

A tower is evaluated from the top: $3\uparrow\uparrow3=3^{(3^3)}=3^{27}$, not $(3^3)^3=19683$, because raising to a power is right-associative. ^[2] A number $N$ has $\lfloor\log_{10}N\rfloor+1$ digits, and $\log_{10}a^e=e\log_{10}a$. So $3\uparrow\uparrow3$ has $13$ digits, but $3\uparrow\uparrow4=3^{7625597484987}$ has $\lfloor3^{27}\log_{10}3\rfloor+1$${}=3638334640025$ of them. For our base, $1777\uparrow\uparrow2=1777^{1777}$ already has $5775$ digits, and the number of digits of $1777\uparrow\uparrow3$ is itself a number with $5776$ digits. No computer can hold even the third level of the tower, so we must work with remainders only.

2. Last digits are remainders

The last eight digits of a number $N$ form its remainder $N\bmod10^8$ after division by $10^8$. We write $x\equiv y\pmod m$ when $m$ divides $x-y$. Congruences can be multiplied, so a product may be reduced modulo $m$ after every step. ^[3] Hence $a^e\bmod m$ is easy to compute, with numbers below $m^2$, for any exponent $e$ that we know. But the exponent of $1777\uparrow\uparrow1855$ is $1777\uparrow\uparrow1854$, which we cannot even write down, so we must find out how much of an exponent really matters.

3. Powers repeat: the last digit of $3^e$

The powers $3^1,3^2,3^3,\dots$ end in the digits $3,9,7,1,3,9,7,1,\dots$ Since $3^4=81\equiv1\pmod{10}$, every further factor $3^4$ keeps the last digit, which therefore depends only on $e\bmod4$. For example $27=6\cdot4+3$, so $3^{27}$ ends like $3^3=27$, and indeed $3^{27}=7625597484987$ ends in $7$. The cycle length $4$ equals the number of last digits $1,3,7,9$ that are coprime to $10$, and this is no coincidence.

4. Euler's theorem

Euler's totient $\varphi(m)$ counts the numbers $1\le k\le m$ with $\gcd(k,m)=1$. For a prime power, removing the $p^{k-1}$ multiples of $p$ leaves $\varphi(p^k)=p^{k-1}(p-1)$, and $\varphi(xy)=\varphi(x)\,\varphi(y)$ for coprime $x,y$, ^[4] so for $a,b\ge1$

$$\varphi(2^a5^b)=2^{a-1}\cdot4\cdot5^{b-1}=2^{a+1}5^{b-1};$$

for instance $\varphi(100)=40$ and $\varphi(10^8)=4\cdot10^7$.

Euler's theorem. If $\gcd(a,m)=1$, then $a^{\varphi(m)}\equiv1\pmod m$. ^[5]

Proof. Let $r_1,\dots,r_k$, where $k=\varphi(m)$, be the numbers from $1$ to $m$ that are coprime to $m$. The remainders of $ar_1,\dots,ar_k$ modulo $m$ are coprime to $m$ and pairwise different, since $m\mid a(r_i-r_j)$ forces $m\mid r_i-r_j$ when $\gcd(a,m)=1$. So they are the $r_i$ in another order; for $a=3$ and $m=10$, the products $3,9,21,27$ leave $3,9,1,7$. Multiplying them all gives $a^kP\equiv P\pmod m$ with $P=r_1\cdots r_k$, and as $P$ is coprime to $m$, $m$ divides $a^k-1$. $\square$

Consequently, if $x\ge y\ge0$ and $x\equiv y\pmod{\varphi(m)}$, then

$$\begin{aligned}a^x&=a^y\bigl(a^{\varphi(m)}\bigr)^{(x-y)/\varphi(m)}\\&\equiv a^y\pmod m:\end{aligned}$$

only the exponent modulo $\varphi(m)$ matters. ^[5]

5. One level at a time

For a base $a$, let $R(h,m)$ be the remainder of $a\uparrow\uparrow h$ modulo $m$. Then $R(1,m)=a\bmod m$ and $R(h,1)=0$, and for $h\ge2$ and $\gcd(a,m)=1$

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

Indeed, $a\uparrow\uparrow h=a^x$ with $x=a\uparrow\uparrow(h-1)$, and $y=R(h-1,\varphi(m))$ is the remainder of $x$ modulo $\varphi(m)$, so $0\le y\le x$, $x\equiv y\pmod{\varphi(m)}$, and Section 4 gives $a^x\equiv a^y\pmod m$. A tower of height $h$ modulo $m$ is thus reduced to a tower of height $h-1$ modulo the smaller number $\varphi(m)$. Repeating this needs $a$ to be coprime to every member of the chain $m,\varphi(m),\varphi(\varphi(m)),\dots$, and the descent stops when the height or the modulus reaches $1$.

6. Worked example: the last two digits of $3\uparrow\uparrow3$ and $3\uparrow\uparrow4$

For $m=100$ the chain is $100,40,16,8,4,2,1$, and all its members are coprime to $3$. For $3\uparrow\uparrow3$, from the top of the tower down, $R(1,16)=3$, $R(2,40)=3^3\bmod40=27$ and $R(3,100)=3^{27}\bmod100=87$, and indeed $7625597484987$ ends in $87$. For $3\uparrow\uparrow4$ the same steps start one level deeper: $R(1,8)=3$, $R(2,16)=27\bmod16=11$, $R(3,40)=3^{11}\bmod40$${}=177147\bmod40=27$, and again $R(4,100)=87$. So $3\uparrow\uparrow4$, with its $3638334640025$ digits, also ends in $87$. Every taller tower of $3$s ends in $87$ as well: the rule gives $87$ for the heights $5$, $6$ and $7$, and from the height $7$ on the descent ends at the modulus $1$, so the height no longer matters.

7. The chain of $10^8$

Let $m_0=10^8=2^85^8$ and $m_{i+1}=\varphi(m_i)$. By Section 4 each step multiplies by $2/5$ until the factors $5$ are gone, and after that each step halves:

$$\begin{aligned}m_i&=4^i\cdot10^{8-i}&&(0\le i\le8),\\m_i&=2^{24-i}&&(8\le i\le24).\end{aligned}$$

The chain runs $10^8$, $4\cdot10^7$, $16\cdot10^6$, …, $65536$, $32768$, …, $2$, $1$ and has $24$ steps. The base $1777$ is odd and not divisible by $5$ (it is a prime), so it is coprime to every $m_i$, and Section 5 applies at every level. The descent for $1777\uparrow\uparrow1855$ reaches $m_{24}=1$ at the height $1831$, where the remainder is $0$, and $24$ modular powers lead back up to $R(1855,10^8)$. Every height of at least $25$ leads to the same computation, so every tower of at least $25$ copies of $1777$ has the same last eight digits; evaluating the lower towers shows that these digits in fact stop changing from the height $8$ on.

8. Every totient chain is short

For $m\ge3$, $\varphi(m)$ is even, ^[4] because $k\mapsto m-k$ pairs off the numbers coprime to $m$, and a number paired with itself, $k=m/2\ge2$, would share the factor $k$ with $m$. For even $m$, $\varphi(m)\le m/2$, because no even number is coprime to $m$. So a chain that starts at an even $m_0$ stays even until it reaches $1$ and at least halves in every step: $m_i\le m_0/2^i$. Its last member before $1$ is at least $2$, so it has at most $\log_2m_0$ steps, at most $26$ for $10^8$; an odd start adds at most one step. However tall the tower, about $\log_2m$ levels suffice.

9. Fast modular powers

Each level needs one power $a^e\bmod m$ with $e\lt\varphi(m)$, so the exponent can have eight digits. Repeated squaring needs only about $2\log_2e$ multiplications. ^[6] For $3^{27}\bmod100$, with $27=11011_2=16+8+2+1$, we square, $3^2=9$, $3^4=81$, $3^8\equiv61$ and $3^{16}\equiv61^2\equiv21\pmod{100}$, and multiply the powers that belong to the binary digits $1$: $3\cdot9=27$, $27\cdot61\equiv47$ and $47\cdot21\equiv87\pmod{100}$. That is $7$ multiplications instead of $26$; the C++ loop also multiplies its start value $1$ by $3$ and squares once more at the end, $9$ in all.

10. Shared primes and shorter periods

Euler's theorem needs $\gcd(a,m)=1$: modulo $256$, the powers of $2$ run through $2,4,\dots,128$ and then stay $0$, never returning to $2$. If $r$ is the largest exponent in the prime factorisation of $m$, the powers are still periodic from the exponent $r$ on, ^[7] ^[8] so that for $x\ge r$

$$a^x\equiv a^{(x\bmod\varphi(m))+\varphi(m)}\pmod m.$$

Both exponents are at least $r$, since $\varphi(m)\ge2^{r-1}\ge r$, so both sides are divisible by the full power in $m$ of every prime that divides $a$, and Euler's theorem handles the other prime powers of $m$, because the two exponents differ by a multiple of $\varphi(m)$. The published programs use this rule when the base and the modulus share a prime; Problem 188 never needs it.

Periods shorter than $\varphi(m)$ work as well; the powers of $3$ modulo $100$, for instance, repeat every $20$ steps. Carmichael's function $\lambda(m)$, the least positive exponent with $a^{\lambda(m)}\equiv1\pmod m$ for all $a$ coprime to $m$, divides $\varphi(m)$, ^[7] and $\lambda(10^8)=\mathrm{lcm}(\lambda(2^8),\lambda(5^8))$${}=\mathrm{lcm}(64,312500)=5\cdot10^6$ gives a chain of $10$ steps instead of $24$.

How the Code Works

The C++ program ^[10] takes the base, the height and the modulus, by default $1777$, $1855$ and $10^8$, from the options --base=, --height= and --mod= in parse_arguments. Unless --skip-checkpoints is given, run_checkpoints requires tetration_mod(3, 3, 100) to return $87$, the value of Section 6. mul_mod multiplies in unsigned __int128, so no product overflows for a 64-bit modulus, and pow_mod is the repeated squaring of Section 9. phi uses trial division: ^[8] each $p$ with $p^2\le n$ that divides $n$ is divided out completely, and the result becomes result / p * (p - 1); a leftover $n\gt1$ is a prime.

tetration_mod(base, height, mod) is Section 5. It returns $0$ for the modulus $1$, base % mod for the height $1$, and otherwise pow_mod(base, exp, mod), where exp comes from the recursive call with the height lowered by one and the modulus ph = phi(mod); if the base and the modulus are not coprime, ph is added to exp, the rule of Section 10.

The Python and Java programs fix the input and have no options or checkpoint, but repeat the recursion. Python's tetration_mod, with the helper euler_phi, uses math.gcd and the built-in three-argument pow on unbounded integers, and its $25$ nested calls stay far below the default recursion limit. Java's eulerPhi, tetMod and gcd work on long and compute the power with BigInteger.modPow.

The code applies the rule of Section 10 without checking that the exponent is at least $r$. For a base $a\ge2$ this is safe when the tower is at least four levels taller than its chain of moduli, since every exponent involved is then at least $2\uparrow\uparrow4=65536$, more than $r$ for any 64-bit modulus, but shorter towers can fail: with --base=2 --height=3 --mod=17 the C++ program prints $1$ instead of $2\uparrow\uparrow3=16$, as at the modulus $16=2^4$ it replaces $2^2=4$ by $2^{2+8}\equiv0$. The option parsers do not check for overflow either. Problem 188 never reaches the branch.

Complexity and Verification

The recursion makes at most one call per member of the chain, so by Section 8 at most about $\log_2m+2$ calls, whatever the height. Counting each operation on 64-bit numbers as one step, each call costs a trial division of at most about $\sqrt m$ steps and a power of about $2\log_2m$ multiplications, so the time is $O(\log m\,(\sqrt m+\log m))$, and the memory, the depth of the recursion, is $O(\log m)$. The main computation of Problem 188 makes $25$ calls; the trial-division loop runs only $44$ times in all, because $n$ shrinks as its factors $2$ and $5$ are removed, and the C++ pow_mod makes $445$ multiplications, at most $52$ per power, since every exponent is below $4\cdot10^7\lt2^{26}$. Each program finishes in a few hundredths of a second on an Apple M4 Max laptop.

Besides the C++ checkpoint, we checked the following, which is not part of the published solutions.

The three programs print the same eight digits.
A Python copy of the recursion was compared with exact values for every modulus up to $1000$, the heights $1$ to $3$ for the bases $2$ to $12$, the height $4$ for the bases $2$ to $6$ and the heights $5$ and $6$ for the base $2$: $40000$ cases. It is right in all $20901$ cases that avoid the branch of Section 10 and in all $14429$ cases in which every exponent the branch meets is at least $r$; among the other $4670$ cases, $337$ are wrong.
An independent computation modulo $2^8$ and $5^8$, which reduces every exponent modulo the order of $1777$ and combines the two remainders by the Chinese remainder theorem, ^[9] agrees with the recursion for every height from $1$ to $60$ and for $1855$.

Footnotes and References

The references below supply the background facts; the descent along the chain of $10^8$, its length, the examples and the operation counts are derived in this article.

Project Euler 188 — The Hyperexponentiation of a Number. The official statement defines a↑↑1 = a and a↑↑(k + 1) = a^(a↑↑k), gives 3↑↑2, 3↑↑3 and the size of 3↑↑4, and asks for the last 8 digits of 1777↑↑1855.
Wikipedia — Tetration. Tetration is iterated exponentiation, written a↑↑n in Knuth's up-arrow notation; nested exponents are calculated from right to left, since raising to a power is right-associative.
Wikipedia — Modular arithmetic. Congruence is compatible with multiplication: a₁ ≡ b₁ and a₂ ≡ b₂ (mod m) imply a₁a₂ ≡ b₁b₂ (mod m).
Wikipedia — Euler's totient function. φ(pᵏ) = pᵏ⁻¹(p − 1) for a prime p, φ is multiplicative, and φ(n) is even for n ≥ 3.
Wikipedia — Euler's theorem. If a and n are coprime, then a^φ(n) ≡ 1 (mod n); one proof shows that multiplication by a permutes a reduced residue system, and x ≡ y (mod φ(n)) implies aˣ ≡ aʸ (mod n).
Wikipedia — Modular exponentiation. The right-to-left binary method squares once per binary digit of the exponent and multiplies into the result where the digit is 1; its running time is O(log e).
Wikipedia — Carmichael function. λ(n) is the least positive m with aᵐ ≡ 1 (mod n) for all a coprime to n; it divides φ(n), equals φ on odd prime powers and half of φ on 2ʳ with r ≥ 3, and is the least common multiple of its values on the prime powers of n. For all a and all r ≥ r_max, the largest exponent in the factorisation of n, aʳ ≡ a^(λ(n) + r) (mod n).
cp-algorithms — Euler's totient function. The page computes φ(n) by trial division in O(√n) and states xⁿ ≡ x^(φ(m) + [n mod φ(m)]) (mod m) for arbitrary x, m and n ≥ log₂ m.
Wikipedia — Chinese remainder theorem. For pairwise coprime moduli, given remainders determine exactly one remainder modulo their product.
C++ — Euler188.cpp. The linked immutable revision contains phi, pow_mod, tetration_mod and run_checkpoints; it is the implementation record for this article.

Problem 188 source code

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    u64 base = 1777;
    int height = 1855;
    u64 mod = 100000000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--base=", options.base) ||
            parse_int_after_prefix(arg, "--height=", options.height) ||
            parse_u64_after_prefix(arg, "--mod=", options.mod)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.height >= 1 && options.mod >= 1;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}

u64 pow_mod(u64 base, u64 exp, const u64 mod) {
    u64 result = 1 % mod;
    base %= mod;

    while (exp > 0) {
        if ((exp & 1ULL) != 0ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1ULL;
    }

    return result;
}

u64 phi(u64 n) {
    u64 result = n;
    for (u64 p = 2; p * p <= n; ++p) {
        if (n % p != 0) {
            continue;
        }
        while (n % p == 0) {
            n /= p;
        }
        result = result / p * (p - 1);
    }
    if (n > 1) {
        result = result / n * (n - 1);
    }
    return result;
}

u64 tetration_mod(const u64 base, const int height, const u64 mod) {
    if (mod == 1) {
        return 0;
    }
    if (height == 1) {
        return base % mod;
    }

    const u64 ph = phi(mod);
    u64 exp = tetration_mod(base, height - 1, ph);
    if (std::gcd(base, mod) != 1ULL) {
        exp += ph;
    }

    return pow_mod(base, exp, mod);
}

bool run_checkpoints() {
    if (tetration_mod(3, 3, 100) != 87ULL) {
        std::cerr << "Checkpoint failed for 3^^3 mod 100" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << tetration_mod(options.base, options.height, options.mod) << '\n';
    return 0;
}

Python

# Problem 188: The hyperexponentiation of a number.
# Compute 1777↑↑1855 mod 10^8 using Euler's theorem.

from math import gcd

def solve():
    base = 1777
    height = 1855
    mod = 10**8

    def euler_phi(n):
        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(b, h, m):
        if m == 1: return 0
        if h == 1: return b % m
        ph = euler_phi(m)
        exp = tetration_mod(b, h-1, ph)
        if gcd(b, m) != 1:
            exp += ph
        return pow(b, exp, m)

    print(tetration_mod(base, height, mod))

solve()

Java

import java.math.BigInteger;

public class Euler188 {
    static long eulerPhi(long n) {
        long r = n;
        for (long p = 2; p * p <= n; p++) {
            if (n % p != 0)
                continue;
            while (n % p == 0)
                n /= p;
            r -= r / p;
        }
        if (n > 1)
            r -= r / n;
        return r;
    }

    static long tetMod(long b, int h, long m) {
        if (m == 1)
            return 0;
        if (h == 1)
            return b % m;
        long ph = eulerPhi(m), exp = tetMod(b, h - 1, ph);
        if (gcd(b, m) != 1)
            exp += ph;
        return BigInteger.valueOf(b).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(m)).longValue();
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(tetMod(1777, 1855, 100000000L));
    }
}