Problem 855: Power Sequence

Mathematical Analysis

Euler’s Theorem for Modular Tetration

Theorem (Euler). If $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Corollary. $a^b \equiv a^{b \bmod \varphi(m)} \pmod{m}$ when $\gcd(a, m) = 1$ and $b \ge \log_2 m$.

Recursive Reduction

To compute ${}^n a \bmod m$:

1. If $m = 1$, return 0.
2. Compute $e = {}^{n-1} a \bmod \varphi(m)$ recursively.
3. Return $a^e \bmod m$.

The recursion terminates because $\varphi(\varphi(\cdots(m))) = 1$ after $O(\log m)$ steps.

Theorem. The tower $\varphi^{(k)}(m) = 1$ after at most $O(\log m)$ iterations, since $\varphi(m) \le m/2$ for $m > 1$.

Lifting the Exponent Lemma

When $\gcd(a, m) > 1$, we need more care. If $a^k \equiv 0 \pmod{m}$ for some small $k$, and the tower height exceeds $k$, the answer is 0.

Concrete Examples

Verification for ${}^3 2 \bmod 10$: ${}^3 2 = 2^{2^2} = 2^4 = 16 \equiv 6 \pmod{10}$. Correct.

Verification for ${}^4 2 \bmod 10$: ${}^4 2 = 2^{{}^3 2} = 2^{16} = 65536 \equiv 6 \pmod{10}$.

Convergence of Tetration Mod $m$

Theorem. For fixed $a$ and $m$ with $\gcd(a, m) = 1$, the sequence ${}^n a \bmod m$ eventually stabilizes (becomes constant) for $n \ge \lceil\log_2 m\rceil$.

Complexity Analysis

• Recursive $\varphi$-reduction: $O(\log^2 m)$ for the recursion depth times modular exponentiation.
• Computing $\varphi$: $O(\sqrt{m})$ per level via trial division.
• Total: $O(\log m \cdot \sqrt{m})$.

Knuth’s Up-Arrow Notation

Tetration is $a \uparrow\uparrow n = {}^n a$. In Knuth’s notation: $a \uparrow b = a^b$, $a \uparrow\uparrow b = a^{a^{\cdots^a}}$ ($b$ copies). This extends to higher hyperoperations: $a \uparrow\uparrow\uparrow b$ (pentation), etc.

Why the Algorithm Terminates

Theorem. The $\varphi$-reduction chain $m, \varphi(m), \varphi(\varphi(m)), \ldots$ reaches 1 after at most $2\log_2 m$ steps.

Proof. For even $m$: $\varphi(m) \le m/2$. For odd $m > 1$: $\varphi(m)$ is even (since $\varphi(n)$ is even for $n > 2$), so the next step halves. Every two steps, the value at least halves. $\square$

Handling $\gcd(a, m) > 1$

When $\gcd(a, m) > 1$, Euler’s theorem doesn’t directly apply. The correct formula is:

The "$+\varphi(m)$" ensures we’re in the periodic regime of $a^k \bmod m$.

Infinite Tetration

Theorem. The infinite tower ${}^\infty a = \lim_{n\to\infty} {}^n a$ converges iff $e^{-e} \le a \le e^{1/e}$, i.e., approximately $0.0660 \le a \le 1.4447$.

For $a = \sqrt{2}$: ${}^\infty \sqrt{2} = 2$ since $(\sqrt{2})^2 = 2$.

For $a = e^{1/e} \approx 1.4447$: ${}^\infty a = e$.

Connection to Ackermann Function

Tetration is equivalent to the Ackermann function at level 3: $A(3, n) = 2^{n+3} - 3$ grows as tetration of 2.

Fixed Points of Modular Tetration

Theorem. For fixed $a$ and $m$, the sequence ${}^n a \bmod m$ is eventually constant. The stabilization index is at most $\text{depth}(\varphi, m)$ where $\text{depth}(\varphi, m) = \min\{k : \varphi^{(k)}(m) = 1\}$.

Answer

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

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

ll power(ll b, ll e, ll m) {
    ll r = 1; b %= m;
    while (e > 0) { if (e&1) r = r*b%m; b = b*b%m; e >>= 1; }
    return r;
}

ll tetration_mod(ll a, ll n, ll m) {
    if (m == 1) return 0;
    if (n == 0) return 1 % m;
    if (n == 1) return a % m;
    ll phi = euler_totient(m);
    ll exp = tetration_mod(a, n-1, phi);
    if (__gcd(a, m) == 1) return power(a, exp, m);
    return power(a, exp + phi, m);
}

int main() {
    assert(tetration_mod(2, 3, 10) == 6);
    assert(tetration_mod(2, 4, 10) == 6);
    cout << tetration_mod(2, 100, 1000000007) << endl;
    return 0;
}

"""
Problem 855: Power Sequence - Modular Tetration

Compute {}^n a mod m using iterated Euler's theorem.
"""
from math import gcd

def euler_totient(n):
    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 tetration_mod(a, n, m):
    """Compute {}^n a mod m."""
    if m == 1: return 0
    if n == 0: return 1 % m
    if n == 1: return a % m
    phi_m = euler_totient(m)
    if gcd(a, m) == 1:
        exp = tetration_mod(a, n - 1, phi_m)
        return pow(a, exp, m)
    else:
        exp = tetration_mod(a, n - 1, phi_m)
        # Need to handle case where a and m share factors
        # For large enough towers, a^tower is divisible by high powers of shared primes
        return pow(a, exp + phi_m, m)  # add phi_m to ensure correct residue

# Direct computation for small cases
def tetration_exact(a, n):
    if n == 0: return 1
    return a ** tetration_exact(a, n - 1)

# Verify
assert tetration_mod(2, 1, 10) == 2
assert tetration_mod(2, 2, 10) == 4
assert tetration_mod(2, 3, 10) == 6
assert tetration_mod(2, 4, 10) == 6
assert tetration_mod(3, 2, 7) == 6

for a in range(2, 6):
    for n in range(0, 5):
        exact = tetration_exact(a, n)
        for m in [7, 10, 13, 100]:
            assert tetration_mod(a, n, m) == exact % m, \
                f"Mismatch: a={a}, n={n}, m={m}"

print("Verification passed!")
print(f"Answer: {tetration_mod(2, 100, 10**9 + 7)}")