Problem 188: The Hyperexponentiation of a Number

Mathematical Analysis

Euler’s Theorem and Iterated Totient

To compute $a^N \pmod{m}$, when $\gcd(a, m)$ might not be 1, we use the generalized version:

For $N \ge \log_2(m)$:

This allows us to reduce the exponent modulo $\phi(m)$, adding $\phi(m)$ to ensure the exponent is large enough.

Iterated Totient Descent

To compute $1777^{1777^{1777^{\cdots}}} \pmod{10^8}$, we recursively reduce the modulus:

The Euler totient function satisfies $\phi(n) < n$ for $n > 1$ and $\phi(n)$ is even for $n > 2$, so the sequence $m_0, m_1, m_2, \ldots$ decreases rapidly and reaches 1 in $O(\log m_0)$ steps.

Computation Chain

The chain of totients reaches 1 well before 1855 levels of recursion, so at sufficient depth the tower value is simply “large enough” and we use the formula with $+\phi(m)$.

Editorial

The recursion depth is at most $O(\log(10^8))$, which is very small (~30 or so). We evaluate the closed-form expressions derived above directly from the relevant parameters and return the resulting value.

Pseudocode

def hyper(a, b, mod):
    If mod == 1 then
        Return 0
    If b == 1 then
        Return a % mod
    exp = hyper(a, b - 1, euler_totient(mod))
    Return pow(a, exp + euler_totient(mod), mod)

The recursion depth is at most $O(\log(10^8))$, which is very small (~30 or so).

## Complexity

- **Time**: $O(\log^2(m))$ where $m = 10^8$, since we recurse $O(\log m)$ times and each modular exponentiation takes $O(\log m)$.
- **Space**: $O(\log m)$ for the recursion stack.

## Answer

$$
\boxed{95962097}
$$

#include <bits/stdc++.h>
using namespace std;

long long euler_totient(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

long long power_mod(long long base, long long exp, long long mod) {
    if (mod == 1) return 0;
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long hyper(long long a, long long b, long long mod) {
    if (mod == 1) return 0;
    if (b == 1) return a % mod;
    long long phi = euler_totient(mod);
    long long exp = hyper(a, b - 1, phi);
    return power_mod(a, exp + phi, mod);
}

int main() {
    cout << hyper(1777, 1855, 100000000) << endl;
    return 0;
}

"""
Problem 188: The Hyperexponentiation of a Number

Find 1777^^1855 mod 10^8 (tetration).
"""

def euler_totient(n):
    """Compute Euler's totient function."""
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

def hyper(a, b, mod):
    """Compute a^^b mod m using iterated totient reduction."""
    if mod == 1:
        return 0
    if b == 1:
        return a % mod
    phi = euler_totient(mod)
    exp = hyper(a, b - 1, phi)
    return pow(a, exp + phi, mod)

def solve():
    result = hyper(1777, 1855, 10**8)
    print(result)

if __name__ == "__main__":
    solve()