Project Euler

Power Tower Modular Arithmetic

Define a power tower T(a, n) recursively: T(a, 1) = a and T(a, n) = a^(T(a, n-1)) for n >= 2. Find T(2, 100) mod (10^9 + 7).

Source sync Apr 19, 2026

Problem #0940

Level Level 20

Solved By 617

Languages C++, Python

Answer 969134784

Length 360 words

number_theorymodular_arithmeticrecursion

The Fibonacci sequence $(f_i)$ is the unique sequence such that

$f_0 = 0$
$f_1 = 1$
$f_{i + 1} = f_i + f{i - 1}$

Similarly, there is a unique function $A(m,n)$ such that

$A(0, 0) = 0$
$A(0, 1) = 1$
$A(m + 1, n) = A(m, n + 1) + A(m, n)$
$A(m + 1, n + 1) = 2A(m + 1, n) + A(m, n)$

Define $S(k)=\displaystyle \sum _{i=2}^k\sum _{j=2}^k A(f_i,f_j)$. For example \begin {align} S(3)&=A(1,1)+A(1,2)+A(2,1)+A(2,2)\\ &=2+5+7+16\\ &=30 \end {align}

You are also given $S(5)=10396$.

Find $S(50)$, giving your answer modulo $1123581313$.

Problem 940: Power Tower Modular Arithmetic

Mathematical Foundation

Theorem 1 (Euler’s theorem). If $\gcd(a, m) = 1$ , then $a^{\varphi(m)} \equiv 1 \pmod{m}$ , where $\varphi$ is Euler’s totient function.

Proof. The elements $\{a \cdot r : r \in (\mathbb{Z}/m\mathbb{Z})^*\}$ form a permutation of $(\mathbb{Z}/m\mathbb{Z})^*$ . Taking the product of all elements: $a^{\varphi(m)} \prod r \equiv \prod r \pmod{m}$ . Since $\prod r$ is coprime to $m$ , we may cancel it. $\square$

Lemma 1 (Exponent reduction). If $\gcd(a, m) = 1$ and $b \geq \log_2 m$ , then:

a^b \equiv a^{b \bmod \varphi(m)} \pmod{m},

where the representative of $b \bmod \varphi(m)$ is taken in $\{0, 1, \ldots, \varphi(m) - 1\}$ , except if $b \bmod \varphi(m) = 0$ and $b > 0$ , we use $\varphi(m)$ instead of $0$ .

Proof. Write $b = q \cdot \varphi(m) + r$ with $0 \leq r < \varphi(m)$ . Then $a^b = (a^{\varphi(m)})^q \cdot a^r \equiv a^r \pmod{m}$ by Theorem 1. The caveat about $r = 0$ ensures correctness when $b > 0$ : we want $a^b \not\equiv a^0 = 1$ in general, but $a^{\varphi(m)} \equiv 1$ , which is consistent since $r = 0$ means $\varphi(m) \mid b$ . $\square$

Theorem 2 (Iterated totient reaches 1). For any $m \geq 2$ , define $\varphi^{(0)}(m) = m$ and $\varphi^{(k+1)}(m) = \varphi(\varphi^{(k)}(m))$ . Then $\varphi^{(k)}(m) = 1$ for all $k \geq \lfloor \log_2 m \rfloor + 1$ .

Proof. For $m \geq 2$ : $\varphi(m) \leq m/2$ (since at least half the integers in $\{1, \ldots, m\}$ are even, and if $m$ is even, $\varphi(m) \leq m/2$ ; if $m$ is odd, $\varphi(m) \leq m - 1 < m$ , and one can show $\varphi(m) \leq m/2$ for $m \geq 3$ by considering the factor of the smallest prime dividing $m$ ). For $m = 2$ : $\varphi(2) = 1$ .

By induction: $\varphi^{(k)}(m) \leq m / 2^k$ . When $m / 2^k < 2$ , i.e., $k > \log_2 m - 1$ , we have $\varphi^{(k)}(m) = 1$ . Thus $k = \lfloor \log_2 m \rfloor + 1$ suffices. $\square$

Theorem 3 (Tower convergence modulo $m$ ). For $a \geq 2$ and $m \geq 2$ , $T(a, n) \bmod m$ stabilizes for $n \geq \lfloor \log_2 m \rfloor + 1$ . In particular, $T(2, 100) \bmod (10^9 + 7) = T(2, 31) \bmod (10^9 + 7)$ .

Proof. By Theorem 2, the iterated totient chain $m, \varphi(m), \varphi^{(2)}(m), \ldots$ reaches 1 in at most $\lfloor \log_2 m \rfloor + 1 \leq 31$ steps (for $m = 10^9 + 7$ ). Once the modulus is 1, all values are 0 mod 1, so deeper levels of the tower do not affect the computation. Since $100 > 31$ , the tower has converged. $\square$

Lemma 2 (Primality of $10^9 + 7$ ). The number $p = 10^9 + 7$ is prime, so $\varphi(p) = p - 1 = 10^9 + 6$ .

Proof. Verified by standard primality testing (e.g., Miller—Rabin with sufficient witnesses, or the AKS algorithm). $\square$

Editorial

Compute T(2, 100) mod (10^9 + 7), where T(a, n) = a^a^a^…^a (n copies of a) evaluated right-to-left (power tower / tetration). Key technique: By Euler’s theorem, a^x mod m = a^(x mod phi(m)) mod m (when gcd(a,m)=1). We recursively reduce the exponent modulo the iterated totient chain: m -> phi(m) -> phi(phi(m)) -> … -> 1 The chain from 10^9+7 has finite length, so the tower stabilizes. Results:. We base cases. We then by Lemma 1, we need T(a, n-1) mod phi(m). Finally, handle the case where exponent == 0 but actual value > 0.

Pseudocode

Base cases
Recursive case: T(a, n) = a^{T(a, n-1)} mod m
By Lemma 1, we need T(a, n-1) mod phi(m)
Handle the case where exponent == 0 but actual value > 0
Since a = 2 and n >= 2, T(2, n-1) >= 2, so exponent should
be interpreted correctly
Main call

Complexity Analysis

Time: The recursion depth is at most $d = \lfloor \log_2 m \rfloor + 1 \approx 30$ . At each level, we compute $\varphi(m_i)$ in $O(\sqrt{m_i})$ and perform modular exponentiation in $O(\log m_i)$ . The dominant cost is the totient computation at the top level: $O(\sqrt{m})$ . Total: $O(d \cdot \sqrt{m}) = O(\sqrt{m} \log m)$ .
Space: $O(d) = O(\log m)$ for the recursion stack.

Answer

\boxed{969134784}

C++ project_euler/problem_940/solution.cpp

#include <bits/stdc++.h>
using namespace std;
long long euler_phi(long long n){
    long long r=n,t=n;
    for(long long p=2;p*p<=t;p++){
        if(t%p==0){while(t%p==0)t/=p;r-=r/p;}
    }
    if(t>1) r-=r/t;
    return r;
}
long long power(long long a,long long b,long long m){
    long long r=1; a%=m;
    while(b>0){if(b&1) r=r*a%m; a=a*a%m; b>>=1;}
    return r;
}
long long tower(long long a,int n,long long m){
    if(m==1) return 0;
    if(n==1) return a%m;
    long long phi=euler_phi(m);
    long long exp=tower(a,n-1,phi);
    return power(a,exp,m);
}
int main(){
    cout<<tower(2,100,1000000007LL)<<endl;
}

Python project_euler/problem_940/solution.py

"""
Problem 940: Power Tower Modular Arithmetic

Compute T(2, 100) mod (10^9 + 7), where T(a, n) = a^a^a^...^a (n copies of a)
evaluated right-to-left (power tower / tetration).

Key technique:
    By Euler's theorem, a^x mod m = a^(x mod phi(m)) mod m (when gcd(a,m)=1).
    We recursively reduce the exponent modulo the iterated totient chain:
        m -> phi(m) -> phi(phi(m)) -> ... -> 1
    The chain from 10^9+7 has finite length, so the tower stabilizes.

Results:
    - T(2, 1) = 2
    - T(2, 2) = 4
    - T(2, 3) = 16
    - T(2, 4) = 65536
    - T(2, 100) mod (10^9+7) computed below

Methods:
    1. euler_totient       -- compute phi(n) via trial division
    2. tower_mod           -- recursive power tower modular evaluation
    3. totient_chain       -- iterated totient chain from m down to 1
    4. tower_brute_small   -- brute-force for small cases (verification)
"""

MOD = 10**9 + 7

def euler_totient(n):
    """Compute phi(n) via trial division."""
    result = n
    temp = n
    p = 2
    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 tower_mod(a, n, m):
    """Compute a^^n mod m (a^a^...^a, n copies, right-to-left)."""
    if m == 1:
        return 0
    if n == 1:
        return a % m
    phi_m = euler_totient(m)
    exp = tower_mod(a, n - 1, phi_m)
    return pow(a, exp, m)

def totient_chain(m):
    """Return [m, phi(m), phi(phi(m)), ..., 1]."""
    chain = [m]
    x = m
    while x > 1:
        x = euler_totient(x)
        chain.append(x)
    return chain

def tower_brute(a, n):
    """Exact a^^n for small n (no mod). WARNING: grows super-exponentially."""
    if n == 1:
        return a
    return a ** tower_brute(a, n - 1)

# Verification
assert tower_brute(2, 1) == 2
assert tower_brute(2, 2) == 4
assert tower_brute(2, 3) == 16
assert tower_brute(2, 4) == 65536

assert tower_mod(2, 1, MOD) == 2
assert tower_mod(2, 2, MOD) == 4
assert tower_mod(2, 3, MOD) == 16
assert tower_mod(2, 4, MOD) == 65536

# Final answer
answer = tower_mod(2, 100, MOD)
print(answer)