Problem 492: Totient Chains

Mathematical Foundation

Theorem 1 (Strict decrease of $\varphi$). For all $n \geq 2$, $\varphi(n) < n$.

Proof. If $n \geq 2$, then $n$ has at least one prime factor $p$. By the Euler product formula, $\varphi(n) = n \prod_{p \mid n}(1 - 1/p)$. Since at least one factor $(1 - 1/p) < 1$, and all factors are at most $1$, we get $\varphi(n) < n$. $\square$

Theorem 2 (Finiteness and well-definedness of $L$). For every $n \geq 1$, the totient chain $n, \varphi(n), \varphi^{(2)}(n), \ldots$ reaches $1$ in finitely many steps. Specifically, $L(1) = 0$ and $L(n) = 1 + L(\varphi(n))$ for $n \geq 2$.

Proof. By Theorem 1, the sequence $n > \varphi(n) > \varphi^{(2)}(n) > \cdots$ is strictly decreasing for all terms $\geq 2$. Since it is a sequence of positive integers bounded below by $1$, it must reach $1$ in finitely many steps. The recurrence follows immediately from the definition: one step from $n$ to $\varphi(n)$, then $L(\varphi(n))$ additional steps. $\square$

Lemma 1 (Logarithmic bound on chain length). For all $n \geq 1$, $L(n) \leq 2\log_2 n + 1$.

Proof. For $n \leq 2$, this is immediate ($L(1) = 0$, $L(2) = 1$). For $n \geq 3$, $\varphi(n)$ is even (since $n$ has an odd prime factor $p$ contributing $p - 1$ which is even, or $n$ is a power of $2$). For even $m \geq 2$, $\varphi(m) \leq m/2$ (since $m = 2^a \cdot k$ gives $\varphi(m) \leq m/2$). Thus after at most one step to reach an even number, each subsequent step halves the value at worst, yielding $L(n) \leq 1 + \log_2 n + 1$. A tighter analysis gives $L(n) = O(\log n)$. $\square$

Theorem 3 (Correctness of sieve computation of $\varphi$). The Euler product sieve correctly computes $\varphi(n)$ for all $n \leq N$ by initializing $\varphi[n] = n$ and, for each prime $p$ (detected when $\varphi[p] = p$), updating $\varphi[kp] \leftarrow \varphi[kp] \cdot (p-1)/p$ for all multiples $kp \leq N$.

Proof. By the Euler product formula, $\varphi(n) = n \prod_{p \mid n}(1 - 1/p)$. The sieve processes each prime $p$ exactly once and multiplies $\varphi[n]$ by $(1 - 1/p)$ for every $n$ divisible by $p$. After all primes $p \leq N$ have been processed, $\varphi[n] = n \prod_{p \mid n}(1 - 1/p)$, which is the correct value. $\square$

Editorial

Iterated Euler totient: phi^(k)(n) until reaching 1. L(n) = chain length (steps to reach 1). Compute sum of L(n) for n = 2..N. We euler product sieve for phi. Finally, compute chain lengths bottom-up.

Pseudocode

Euler product sieve for phi
Compute chain lengths bottom-up

Complexity Analysis

• Time: $O(N \log \log N)$ for the Euler product sieve (each integer $n$ is visited by each of its $O(\log \log n)$ distinct prime factors on average), plus $O(N)$ for chain length computation. Total: $O(N \log \log N)$.
• Space: $O(N)$ for the arrays $\varphi[\cdot]$ and $L[\cdot]$.

Answer

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

int main() {
    const int LIMIT = 1000;

    // Totient sieve
    vector<int> phi(LIMIT + 1);
    iota(phi.begin(), phi.end(), 0);
    for (int p = 2; p <= LIMIT; p++) {
        if (phi[p] == p) { // p is prime
            for (int m = p; m <= LIMIT; m += p) {
                phi[m] = phi[m] / p * (p - 1);
            }
        }
    }

    // Chain lengths
    vector<int> L(LIMIT + 1, 0);
    for (int n = 2; n <= LIMIT; n++) {
        L[n] = 1 + L[phi[n]];
    }

    // Sum of chain lengths
    long long total = 0;
    for (int n = 2; n <= LIMIT; n++) {
        total += L[n];
    }

    cout << "Sum of L(n) for n=2.." << LIMIT << ": " << total << endl;

    // Print some chain lengths
    cout << "\nChain lengths:" << endl;
    for (int n = 2; n <= 20; n++) {
        cout << "L(" << n << ") = " << L[n];
        // Print chain
        cout << "  chain: " << n;
        int x = n;
        while (x > 1) {
            x = phi[x];
            cout << " -> " << x;
        }
        cout << endl;
    }

    return 0;
}

"""
Problem 492: Totient Chains
Iterated Euler totient: phi^(k)(n) until reaching 1.
L(n) = chain length (steps to reach 1).
Compute sum of L(n) for n = 2..N.
"""

def totient_sieve(limit: int) -> list:
    """Compute phi(n) for n = 0..limit."""
    phi = list(range(limit + 1))
    for p in range(2, limit + 1):
        if phi[p] == p:  # p is prime
            for m in range(p, limit + 1, p):
                phi[m] = phi[m] // p * (p - 1)
    return phi

def chain_lengths(limit: int):
    """Compute L(n) = totient chain length for n = 0..limit.
    Returns (phi, L) arrays."""
    phi = totient_sieve(limit)
    L = [0] * (limit + 1)
    for n in range(2, limit + 1):
        L[n] = 1 + L[phi[n]]
    return phi, L

def totient_chain(n: int, phi: list) -> list:
    """Return the full totient chain starting at n."""
    chain = [n]
    while n > 1:
        n = phi[n]
        chain.append(n)
    return chain

def solve(limit: int):
    """Sum of L(n) for n = 2..limit."""
    _, L = chain_lengths(limit)
    return sum(L[2:])

# Compute and display
limit = 1000
phi, L = chain_lengths(limit)

print("Totient chains for small n:")
for n in range(2, 21):
    chain = totient_chain(n, phi)
    print(f"  n={n:2d}: chain = {' -> '.join(map(str, chain))}, L({n}) = {L[n]}")

answer_100 = sum(L[2:101])
answer_1000 = sum(L[2:1001])
print(f"\nSum of L(n) for n=2..100:  {answer_100}")
print(f"Sum of L(n) for n=2..1000: {answer_1000}")