Problem 282: The Ackermann Function

Mathematical Development

Theorem 1 (Closed Forms for Ackermann Levels 0—4)

Theorem. For all $m \ge 0$:

1. $\operatorname{ack}(0, m) = m + 1$.
2. $\operatorname{ack}(1, m) = m + 2$.
3. $\operatorname{ack}(2, m) = 2m + 3$.
4. $\operatorname{ack}(3, m) = 2^{m+3} - 3$.
5. $\operatorname{ack}(4, m) = \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{m+3} - 3 = {}^{m+3}2 - 3$.

Proof. Each level is established by induction on $m$.

(1) By definition.

(2) Base case: $\operatorname{ack}(1,0) = \operatorname{ack}(0,1) = 2 = 0 + 2$. Inductive step: $\operatorname{ack}(1,m) = \operatorname{ack}(0, \operatorname{ack}(1, m-1)) = \operatorname{ack}(1,m-1) + 1$. By the inductive hypothesis $\operatorname{ack}(1,m-1) = m+1$, so $\operatorname{ack}(1,m) = m+2$.

(3) Base case: $\operatorname{ack}(2,0) = \operatorname{ack}(1,1) = 3 = 2 \cdot 0 + 3$. Inductive step: $\operatorname{ack}(2,m) = \operatorname{ack}(1, \operatorname{ack}(2,m-1)) = \operatorname{ack}(2,m-1) + 2 = (2(m-1)+3) + 2 = 2m+3$.

(4) Base case: $\operatorname{ack}(3,0) = \operatorname{ack}(2,1) = 5 = 2^3 - 3$. Inductive step: $\operatorname{ack}(3,m) = \operatorname{ack}(2, \operatorname{ack}(3,m-1)) = 2\operatorname{ack}(3,m-1) + 3 = 2(2^{m+2}-3)+3 = 2^{m+3}-3$.

(5) Base case: $\operatorname{ack}(4,0) = \operatorname{ack}(3,1) = 2^4 - 3 = 13 = {}^{3}2 - 3$. Inductive step: $\operatorname{ack}(4,m) = \operatorname{ack}(3, \operatorname{ack}(4,m-1)) = 2^{\operatorname{ack}(4,m-1)+3} - 3 = 2^{{}^{m+2}2} - 3 = {}^{m+3}2 - 3$. $\qquad \blacksquare$

Corollary. The diagonal values are: $A(0) = 1$, $A(1) = 3$, $A(2) = 7$, $A(3) = 61$, $A(4) = {}^{7}2 - 3$.

Theorem 2 (Modular Stabilization of Iterated Exponentiation)

Theorem. For any positive integer $M$, there exists a non-negative integer $H$ such that ${}^{h}2 \equiv {}^{H}2 \pmod{M}$ for all $h \ge H$. The minimal such $H$ equals the length of the Carmichael chain $M, \lambda(M), \lambda(\lambda(M)), \ldots, 1$.

Proof. By strong induction on $M$.

Base case: $M = 1$. Then $H = 0$ and the congruence ${}^{h}2 \equiv 0 \pmod{1}$ holds trivially.

Inductive step: Let $M > 1$.

Case 1: $\gcd(2, M) = 1$. By the generalized Euler theorem, $2^a \equiv 2^b \pmod{M}$ whenever $a \equiv b \pmod{\lambda(M)}$, where $\lambda$ is Carmichael’s function. Since $\lambda(M) < M$, the inductive hypothesis applies to $\lambda(M)$: the sequence ${}^{h-1}2 \bmod \lambda(M)$ stabilizes for $h - 1 \ge H'$, where $H'$ is the chain length for $\lambda(M)$. Hence ${}^{h}2 = 2^{{}^{h-1}2} \bmod M$ stabilizes for $h \ge H' + 1$.

Case 2: $2 \mid M$. Write $M = 2^a \cdot M'$ with $\gcd(2, M') = 1$ and $a \ge 1$. For $h \ge a$, the tower ${}^{h}2$ is divisible by $2^a$, so ${}^{h}2 \equiv 0 \pmod{2^a}$. By Case 1, ${}^{h}2 \bmod M'$ stabilizes. By the Chinese Remainder Theorem, ${}^{h}2 \bmod M$ stabilizes. $\qquad \blacksquare$

Theorem 3 (Computation via CRT Decomposition)

Theorem. Let $M = 14^8 = 2^8 \cdot 7^8$. Then:

1. For $k \ge 4$: $A(k) \equiv -3 \equiv 253 \pmod{256}$, since the tower ${}^{h}2$ satisfies ${}^{h}2 \equiv 0 \pmod{256}$ for all $h \ge 8$, and the tower heights in $A(k)$ for $k \ge 4$ exceed $8$.
2. Modulo $7^8$: since $\gcd(2, 7^8) = 1$, we compute via the iterated Carmichael chain. For $A(4) = {}^{7}2 - 3$, we evaluate ${}^{7}2 \bmod 7^8$ by recursing down the chain. For $A(5)$ and $A(6)$, the tower heights vastly exceed the chain length, so the modular residue has stabilized to the same value as ${}^{\infty}2 \bmod 7^8$.
3. The final values are combined via CRT to obtain $A(k) \bmod 14^8$ for each $k \in \{4, 5, 6\}$.

Proof. Part (1): ${}^{h}2 = 2^{{}^{h-1}2}$, and for $h \ge 2$, the exponent ${}^{h-1}2 \ge 4 > 8$ is false only for small $h$; checking, ${}^{2}2 = 4$, ${}^{3}2 = 16$, ${}^{4}2 = 65536$. For $h \ge 4$, the exponent exceeds $8$, giving $2^{(\text{exponent})} \equiv 0 \pmod{2^8}$. For $A(4)$, the tower height is $7 \ge 4$, so ${}^{7}2 \equiv 0 \pmod{256}$ and $A(4) \equiv -3 \pmod{256}$.

Part (2): The Carmichael chain for $7^8$ is $7^8 \to \lambda(7^8) = 6 \cdot 7^7 \to \lambda(6 \cdot 7^7) = \operatorname{lcm}(\lambda(2), \lambda(3), \lambda(7^7)) = \operatorname{lcm}(1, 2, 6 \cdot 7^6) = 6 \cdot 7^6 \to \cdots$, terminating in $O(\log M)$ steps. For $A(5)$: $\operatorname{ack}(5,0) = 65533$ and $\operatorname{ack}(5,1) = {}^{65536}2 - 3$, where the tower height $65536$ already exceeds any conceivable chain length. For subsequent values of $\operatorname{ack}(5, m)$ and all values of $\operatorname{ack}(6, m)$, the tower heights grow hyper-exponentially and yield the same stabilized residue.

Part (3): Standard CRT reconstruction from the residues modulo $2^8$ and $7^8$. $\qquad \blacksquare$

Editorial

Closed forms: A(0)=1, A(1)=3, A(2)=7, A(3)=61, A(4)=2^^7 - 3. A(5) and A(6) involve towers that stabilize modulo 14^8. Computation via CRT (mod 2^8 and mod 7^8) with iterated Carmichael lambda. We compute A(4), A(5), A(6) mod M via tower2_mod. We then compute 2^^height mod m via CRT on 2-part and odd-part. Finally, recurse using Carmichael’s lambda for the odd part.

Pseudocode

Compute A(4), A(5), A(6) mod M via tower2_mod
Compute 2^^height mod m via CRT on 2-part and odd-part
Recurse using Carmichael's lambda for the odd part

Complexity Analysis

• Time: $O(L \cdot \log M)$ where $L = O(\log M)$ is the Carmichael chain length. Each level involves one modular exponentiation costing $O(\log M)$ multiplications. Total: $O(\log^2 M)$.
• Space: $O(L) = O(\log M)$ for the recursion stack.

Answer

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

typedef long long ll;
typedef __int128 lll;

ll powmod(ll a, ll b, ll m) {
    if (m == 1) return 0;
    a %= m;
    if (a < 0) a += m;
    ll result = 1;
    while (b > 0) {
        if (b & 1) result = (lll)result * a % m;
        a = (lll)a * a % m;
        b >>= 1;
    }
    return result;
}

ll euler_phi(ll n) {
    ll result = n;
    for (ll 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;
}

ll carmichael(ll n) {
    ll result = 1;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int e = 0;
            ll pk = 1;
            while (n % p == 0) { n /= p; e++; pk *= p; }
            ll lam = (p == 2 && e >= 3) ? pk / 4 : pk - pk / p;
            result = lcm(result, lam);
        }
    }
    if (n > 1) result = lcm(result, n - 1);
    return result;
}

// Compute 2^^height mod m via CRT on 2-part and odd-part
pair<ll, bool> tower2_mod(int height, ll m) {
    if (m == 1) return {0, true};
    if (height == 0) return {1 % m, 1 >= m};
    if (height == 1) return {2 % m, 2 >= m};

    int v2 = 0;
    ll modd = m;
    while (modd % 2 == 0) { modd /= 2; v2++; }

    // Mod 2^v2
    ll mod_2part = 0;
    if (v2 > 0) {
        ll exp_val;
        if (height - 1 <= 3) {
            ll small[] = {1, 2, 4, 16};
            exp_val = small[height - 1];
        } else {
            exp_val = 65536;
        }
        if (exp_val < v2)
            mod_2part = (1LL << exp_val) % (1LL << v2);
    }

    // Mod odd part
    ll mod_oddpart = 0;
    if (modd > 1) {
        ll lam = carmichael(modd);
        auto [exp_mod, _] = tower2_mod(height - 1, lam);
        mod_oddpart = powmod(2, exp_mod, modd);
    }

    // CRT
    ll result;
    if (v2 == 0) {
        result = mod_oddpart % m;
    } else {
        ll p2 = 1LL << v2;
        ll inv_p2 = powmod(p2 % modd, euler_phi(modd) - 1, modd);
        ll diff = ((mod_oddpart - mod_2part) % modd + modd) % modd;
        ll t = (lll)diff * inv_p2 % modd;
        result = mod_2part + p2 * t;
    }
    return {result % m, true};
}

int main() {
    ll M = 1;
    for (int i = 0; i < 8; i++) M *= 14;

    ll a0 = 1, a1 = 3, a2 = 7, a3 = 61;
    ll a4 = (tower2_mod(7, M).first - 3 + M) % M;
    ll stable = tower2_mod(100, M).first;
    ll a5 = (stable - 3 + M) % M;
    ll a6 = a5;

    cout << (a0 + a1 + a2 + a3 + a4 + a5 + a6) % M << endl;
    return 0;
}

"""
Project Euler Problem 282: The Ackermann Function

Find sum_{n=0}^{6} A(n) mod 14^8 where A(n) = ack(n, n).

Closed forms: A(0)=1, A(1)=3, A(2)=7, A(3)=61, A(4)=2^^7 - 3.
A(5) and A(6) involve towers that stabilize modulo 14^8.

Computation via CRT (mod 2^8 and mod 7^8) with iterated Carmichael lambda.
"""

from sympy.ntheory import factorint
from math import gcd

def carmichael(n):
    if n == 1:
        return 1
    result = 1
    factors = factorint(n)
    for p, e in factors.items():
        if p == 2:
            lam = 1 if e == 1 else (2 if e == 2 else p ** (e - 2))
        else:
            lam = (p - 1) * p ** (e - 1)
        result = result * lam // gcd(result, lam)
    return result

def tower2_mod(height, m):
    if m == 1:
        return 0
    if height == 0:
        return 1 % m
    if height == 1:
        return 2 % m

    v2 = 0
    odd_part = m
    while odd_part % 2 == 0:
        odd_part //= 2
        v2 += 1

    # Mod 2^v2
    if v2 == 0:
        mod_2part, p2 = 0, 1
    else:
        p2 = 1 << v2
        small_towers = {0: 1, 1: 2, 2: 4, 3: 16, 4: 65536}
        exp_val = small_towers.get(height - 1, 10**20)
        mod_2part = 0 if exp_val >= v2 else (1 << exp_val) % p2

    # Mod odd_part
    if odd_part == 1:
        mod_oddpart = 0
    else:
        lam = carmichael(odd_part)
        exp_mod = tower2_mod(height - 1, lam)
        mod_oddpart = pow(2, exp_mod, odd_part)

    # CRT
    if v2 == 0:
        return mod_oddpart % m
    inv_p2 = pow(p2, -1, odd_part)
    diff = (mod_oddpart - mod_2part) % odd_part
    t = diff * inv_p2 % odd_part
    return (mod_2part + p2 * t) % m

M = 14 ** 8
a0, a1, a2, a3 = 1, 3, 7, 61
a4 = (tower2_mod(7, M) - 3) % M
stable = tower2_mod(200, M)
a5 = (stable - 3) % M
a6 = a5

print((a0 + a1 + a2 + a3 + a4 + a5 + a6) % M)