Problem 214: Totient Chains

Mathematical Foundation

Theorem 1 (Euler’s product formula). For $n = p_1^{a_1} \cdots p_k^{a_k}$ with distinct primes $p_i$,

Proof. By inclusion-exclusion on the set $\{1, \ldots, n\}$, the count of integers coprime to $n$ is:

This follows from the Mobius inversion formula: $\phi(n) = \sum_{d \mid n} \mu(d) \cdot (n/d)$, and the multiplicativity of $\mu$. $\square$

Lemma 1 (Strict decrease). For all $n \geq 2$, $\phi(n) < n$. Moreover, $\phi(n) \leq n/2$ when $n$ is even.

Proof. For $n \geq 2$, $n$ has at least one prime factor $p$, so $\phi(n) = n \prod(1 - 1/p_i) \leq n(1 - 1/p) < n$. If $2 \mid n$, then $\phi(n) \leq n(1 - 1/2) = n/2$. $\square$

Theorem 2 (Well-definedness and computability of chain length). The totient chain of every $n \geq 1$ terminates at 1. If $\ell(n)$ denotes the chain length, then $\ell(1) = 1$ and $\ell(n) = 1 + \ell(\phi(n))$ for $n \geq 2$. Moreover, $\ell(n)$ can be computed in order $n = 1, 2, 3, \ldots$ since $\phi(n) < n$.

Proof. Since $\phi(n) < n$ for $n \geq 2$ (Lemma 1), the sequence $n, \phi(n), \phi^2(n), \ldots$ is strictly decreasing until it reaches 1 (since $\phi(1) = 1$). This guarantees termination. The recurrence $\ell(n) = 1 + \ell(\phi(n))$ is valid because the chain of $n$ is $n$ followed by the chain of $\phi(n)$. Since $\phi(n) < n$, processing in increasing order ensures $\ell(\phi(n))$ is already computed when we compute $\ell(n)$. $\square$

Lemma 2 (Totient sieve correctness). Initialize $\phi[n] = n$ for all $n$. For each $n$ from 2 to $N-1$: if $\phi[n] = n$ (i.e., $n$ is prime), then for every multiple $m$ of $n$ with $m < N$, set $\phi[m] \leftarrow \phi[m] \cdot (n-1)/n$. After completion, $\phi[n]$ equals Euler’s totient for all $1 \leq n < N$.

Proof. Each prime $p < N$ is identified when $\phi[p]$ still equals $p$ (no smaller prime has modified it, since $p$ is prime). The update $\phi[m] \leftarrow \phi[m] \cdot (p-1)/p$ applies the factor $(1 - 1/p)$ for each prime $p \mid m$. After all primes are processed, $\phi[n] = n \prod_{p \mid n}(1 - 1/p) = \phi(n)$ by Theorem 1. $\square$

Lemma 3 (Prime detection). After the totient sieve, $n$ is prime if and only if $\phi[n] = n - 1$.

Proof. If $n$ is prime, $\phi(n) = n - 1$. Conversely, if $n$ is composite with smallest prime factor $p \leq \sqrt{n}$, then $\phi(n) \leq n(1 - 1/p) \leq n(1 - 1/\sqrt{n}) < n - 1$ for $n \geq 4$. For $n = 1$, $\phi(1) = 1 \neq 0$. $\square$

Editorial

We totient sieve. We then chain length computation. Finally, sum primes with chain length 25. We first generate the primes required by the search, then enumerate the admissible combinations and retain only the values that satisfy the final test.

Pseudocode

Totient sieve
Chain length computation
Sum primes with chain length 25

Complexity Analysis

• Time: Totient sieve: $O(N \log \log N)$ (each composite is visited once per prime factor, and $\sum_{p \leq N} N/p = O(N \log \log N)$ by Mertens’ theorem). Chain computation: $O(N)$. Prime summation: $O(N)$. Total: $O(N \log \log N)$ where $N = 4 \times 10^7$.
• Space: $O(N)$ for the $\phi$ and chain arrays.

Answer

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

int main() {
    const int N = 40000000;

    // Sieve for Euler's totient
    vector<int> phi(N);
    iota(phi.begin(), phi.end(), 0); // phi[i] = i

    for (int i = 2; i < N; i++) {
        if (phi[i] == i) { // i is prime
            for (int j = i; j < N; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }

    // Compute chain lengths
    vector<int> chain(N, 0);
    chain[1] = 1;
    for (int i = 2; i < N; i++) {
        chain[i] = 1 + chain[phi[i]];
    }

    // Sum primes with chain length 25
    long long answer = 0;
    for (int i = 2; i < N; i++) {
        if (phi[i] == i - 1 && chain[i] == 25) { // i is prime and chain length is 25
            answer += i;
        }
    }

    cout << answer << endl;
    return 0;
}

def solve():
    N = 40_000_000

    # Sieve for Euler's totient
    phi = list(range(N))
    for i in range(2, N):
        if phi[i] == i:  # i is prime
            for j in range(i, N, i):
                phi[j] = phi[j] // i * (i - 1)

    # Compute chain lengths
    chain = [0] * N
    chain[1] = 1
    for i in range(2, N):
        chain[i] = 1 + chain[phi[i]]

    # Sum primes with chain length 25
    answer = 0
    for i in range(2, N):
        if phi[i] == i - 1 and chain[i] == 25:
            answer += i

    print(answer)

if __name__ == "__main__":
    solve()