Problem 214: Totient Chains

Mathematical Development

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 $\{1, \ldots, n\}$, the count of integers coprime to $n$ is

Lemma 1 (Strict decrease). For all $n \geq 2$, $\phi(n) < n$.

Proof. If $n \geq 2$, then $n$ has at least one prime factor $p$, so

$\square$

Theorem 2 (Chain recurrence). If $\ell(n)$ denotes the totient-chain length, then $\ell(1) = 1$ and

for all $n \geq 2$.

Proof. The chain of $n$ is $n$ followed by the chain of $\phi(n)$. Since $\phi(n) < n$ by Lemma 1, repeated iteration must eventually reach 1. $\square$

Lemma 2 (Totient sieve correctness). Initialize $\phi[n] = n$ for all $n$. For each prime $p$, updating every multiple $m$ by

produces the correct totient values for all $m$.

Proof. Each prime divisor $p$ of $m$ contributes exactly one factor $(1 - 1/p)$ in Euler’s product formula, and the sieve applies those factors once per prime divisor. $\square$

Lemma 3 (Prime detection). For $n \geq 2$, we have $\phi(n) = n - 1$ if and only if $n$ is prime.

Proof. If $n$ is prime, then every positive integer below it is coprime to $n$, so $\phi(n) = n - 1$. Conversely, a composite $n$ has a nontrivial prime factor $p$, so at least the multiples of $p$ below $n$ are excluded, forcing $\phi(n) < n - 1$. $\square$

Editorial

The recursion for the chain length is the important structural fact: once $\phi(n)$ is known, the chain length of $n$ is just one more than the chain length of a smaller number. That means a sieve order is perfect for this problem, because when we reach $n$, both $\phi(n)$ and $\ell(\phi(n))$ are already available.

So we combine three tasks in one pass. First compute the totient values with the standard sieve. Then, in increasing order, use

to fill the chain-length array. Whenever $n$ is prime, identified by $\phi(n) = n-1$, check whether the chain length is 25 and add it if it is.

Pseudocode

Set LIMIT = 40,000,000.
Initialize phi[n] = n for 0 <= n < LIMIT.
Initialize chain[1] = 1 and chain[n] = 0 otherwise.
answer = 0

For n from 2 to LIMIT - 1:
    If phi[n] = n:
        For each multiple m of n:
            phi[m] -= phi[m] / n

    chain[n] = chain[phi[n]] + 1

    If phi[n] = n - 1 and chain[n] = 25:
        answer += n

Return answer

Complexity Analysis

• Time: $O(N \log \log N)$ for the totient sieve, plus $O(N)$ for the chain updates and prime filtering.
• Space: $O(N)$ for the totient table and the chain-length table.

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;
}

from array import array


def solve():
    limit = 40_000_000

    phi = array("I", range(limit))
    chain = bytearray(limit)
    chain[1] = 1

    answer = 0

    for n in range(2, limit):
        if phi[n] == n:
            for multiple in range(n, limit, n):
                phi[multiple] -= phi[multiple] // n

        chain[n] = chain[phi[n]] + 1
        if phi[n] == n - 1 and chain[n] == 25:
            answer += n

    print(answer)


if __name__ == "__main__":
    solve()