Problem 214: Totient Chains

Project Euler Problem 214 Solution

EulerSolve provides an optimized solution for Project Euler Problem 214, Totient Chains, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For the Project Euler parameters $N=40{,}000{,}000$ and $T=25$, define the totient chain of a positive integer by repeatedly applying Euler's totient function until the value reaches $1$: $$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$ The problem asks for the sum of all primes $p < N$ whose chain has length exactly $T$. If we denote the chain length by $\ell(n)$, then the target quantity is $$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$ where the sum runs over primes. A naive prime-by-prime search would recompute the same totient values again and again. The implementations avoid that duplication by building one global table of $\varphi(n)$ and one global table of chain lengths. Mathematical Approach The key object is the directed map $n \mapsto \varphi(n)$. For Problem 214, every useful fact comes from understanding how this map behaves on all integers up to the bound, not just on the primes that appear in the final sum. The totient map always moves downward For every integer $n > 1$, Euler's totient satisfies $\varphi(n) < n$. Therefore repeated iteration cannot cycle above $1$; it must eventually terminate at $1$. This makes the chain length well defined for every positive integer. The natural base case is $$\ell(1)=1,$$ because the chain starting at $1$ already consists of a single term....

Detailed mathematical approach

Problem Summary

Euler's totient function $\varphi$ assigns to every positive integer $n$ the number of integers $k$ with $1\le k\le n$ and $\gcd(k,n)=1$. Applying $\varphi$ again and again to a starting number gives a decreasing chain that ends in $1$, and the length of the chain is the number of its terms, the starting number and the final $1$ included: $5$ generates $5,4,2,1$, a chain of length $4$. The statement lists all eight chains of length $4$, which start at $5$, $7$, $8$, $9$, $10$, $12$, $14$ and $18$; the two primes among them give $5+7=12$. We must find the sum of all primes $p\lt 40\,000\,000$ whose chain has length $25$. ^[1]

The whole solution in one sentence: one sieve computes $\varphi(n)$ for every $n$ up to the bound, a second pass fills a table of chain lengths in increasing order, each length being one more than the length for $\varphi(n)$, and a last pass adds up the primes whose chain length is $25$.

Mathematical Approach

We build the method up from small chains; the last section explains the chain lengths by counting factors $2$.

1. Small chains

For $n=1,2,\dots,20$ the totients are

$1, 1, 2, 2, 4, 2, 6, 4, 6, 4,$
$10, 4, 12, 6, 8, 8, 16, 6, 18, 8;$

for example $\varphi(12)=4$, because only $1$, $5$, $7$ and $11$ share no prime factor with $12$. Following these values gives chains such as $11,10,4,2,1$, then $17,16,8,4,2,1$ and $19,18,6,2,1$. Write $\ell(n)$ for the length of the chain of $n$. For $n=1,\dots,20$ the lengths are

$1, 2, 3, 3, 4, 3, 4, 4, 4, 4,$
$5, 4, 5, 4, 5, 5, 6, 4, 5, 5.$

The chains merge: the chain of $11$ continues as the chains of $10$ and of $4$, and the solution exploits exactly this.

2. A rule for the chain length

For $n\ge2$ the number $n$ is not coprime to itself, so $\varphi(n)\le n-1$: the chain decreases until it stops at $1$, where $\varphi(1)=1$. For $m\ge3$ the two numbers $1$ and $m-1$ are coprime to $m$, so $\varphi(m)\ge2$. Hence $\varphi(m)=1$ only for $m=1$ and $m=2$, and every chain that starts at $n\ge2$ ends with $2,1$. Removing the first term of the chain of $n\ge2$ leaves the chain of $\varphi(n)$, so

$$\begin{aligned}\ell(1)&=1,\\ \ell(n)&=1+\ell\bigl(\varphi(n)\bigr)\quad(n\ge2).\end{aligned}$$

Because $\varphi(n)\lt n$, a table $\ell(1),\ell(2),\ell(3),\dots$ filled in increasing order always finds the value it needs already computed. This is dynamic programming: each subproblem, here the length of one chain, is solved once and stored. ^[2] The numbers $\ell(n)-1$, the counts of applications of $\varphi$ needed to reach $1$, form the sequence A003434 of the OEIS, which gives the same recursion. ^[3]

3. What the chains of primes need

For a prime $p$ all $k$ with $1\le k\le p-1$ are coprime to $p$, so $\varphi(p)=p-1$ ^[4] and

$$\ell(p)=1+\ell(p-1).$$

The prime $2$ has the chain $2,1$. For an odd prime $p$ the number $p-1$ is even, and since $\varphi(m)$ is even for $m\ge3$, ^[4] so are all later terms before the final $1$. They vary widely: $41,40,16,8,4,2,1$ passes through $40$ and $16$. The programs therefore keep $\varphi(n)$ and $\ell(n)$ for every $n$ up to the bound. The lengths of odd composite numbers are never used, but their totients are, by the sieve of Section 5, as in $\varphi(30)=(2-1)\,\varphi(15)$. Following the chain of each prime separately, with a factorisation at every step, would compute the same tails again and again.

4. Totients one prime at a time

Two facts about $\varphi$ are needed. The first is Euler's product formula. For $n=12$, remove the $6$ multiples of $2$ and the $4$ multiples of $3$ from $1,\dots,12$, and put back the $2$ multiples of $6$, which were removed twice: $\varphi(12)=12-6-4+2=4$. In general this inclusion–exclusion over the distinct primes $q$ dividing $n$ gives the expanded form of ^[4]

$$\varphi(n)=n\prod_{q\mid n}\Bigl(1-\frac1q\Bigr).$$

The second is multiplicativity: $\varphi(ab)=\varphi(a)\,\varphi(b)$ whenever $\gcd(a,b)=1$, because coprime $a$ and $b$ have no prime divisor in common, so the product for $ab$ splits into the products for $a$ and $b$. Together they give two rules for a number $i\ge2$ and a prime $p$:

$$\varphi(ip)=\begin{cases}p\,\varphi(i), & p\mid i,\\ (p-1)\,\varphi(i), & p\nmid i.\end{cases}$$

If $p$ divides $i$, then $ip$ and $i$ have the same prime divisors, so the product in the formula is the same and only the factor in front grows from $i$ to $ip$. If $p$ does not divide $i$, then $\gcd(i,p)=1$ and $\varphi(ip)=\varphi(i)\,\varphi(p)$${}=(p-1)\,\varphi(i)$. For example, $\varphi(12)=2\,\varphi(6)=4$, $\varphi(15)=(3-1)\,\varphi(5)=8$ and $\varphi(45)=3\,\varphi(15)=24$.

5. The linear sieve

The sieve visits $i=2,3,\dots,N$ in increasing order with the list of the primes found so far. An unmarked $i$ is prime, with $\varphi(i)=i-1$. Then, for the listed primes $p=2,3,5,\dots$ in increasing order, the sieve marks $ip$ as composite and sets $\varphi(ip)$ by Section 4, stopping after the first $p$ that divides $i$ or as soon as $ip\gt N$. So for each $i$ it uses only primes up to the smallest prime factor of $i$.

Claim. Every composite $v\le N$ is marked exactly once, namely at $i=v/p$, where $p$ is the smallest prime factor of $v$.

Proof. Let $p$ be the smallest prime factor of $v$ and $i=v/p$. Every prime factor of $i$ is at least $p$, and $i\ge p$, so all primes up to $p$ are in the list when $i$ is reached. A prime $q\lt p$ does not divide $i$, and $qi\lt v\le N$, so the loop does not stop before $p$, and at $p$ it marks $v$. Conversely, if $v$ is marked at some $i$ with the prime $p$, then $p$ is not larger than any prime factor of $i$, because the loop stops at the first prime that divides $i$. So $p$ is the smallest prime factor of $v$, and $i=v/p$ is determined by $v$. ^[5]

Two consequences make the sieve work. When the loop reaches $i$, a composite $i$ has already been marked, from the smaller number $i/p$ with $p$ its smallest prime factor; so an unmarked $i$ really is prime, and $\varphi(i)$ is known in both cases. And the work is linear: every step of the inner loop either marks a new composite or stops because $ip\gt N$, which happens at most once for each $i$. Gries and Misra observed in 1978 that such a sieve, already used by Euler, runs in linear time; the classical sieve of Eratosthenes needs $O(N\log\log N)$ operations. ^[6]

For $N=20$ the marks, written as $i\cdot p$, are in this order $4=2\cdot2$, $6=3\cdot2$, $9=3\cdot3$, $8=4\cdot2$, $10=5\cdot2$, $15=5\cdot3$, $12=6\cdot2$, $14=7\cdot2$, $16=8\cdot2$, $18=9\cdot2$ and $20=10\cdot2$: each of the $11$ composites once, in $24$ steps of the inner loop, $11$ marks and $13$ stops. The number $18$ is marked from $9$ with the prime $2$, which gives $\varphi(18)=(2-1)\,\varphi(9)=6$, and not from $6$ with the prime $3$, because at $i=6$ the loop stops right after $p=2$.

6. How long a chain can be

Claim. For every $n\ge3$, $\ell(n)\le 2+\log_2(n-1)$.

Proof. Write the chain as $n=a_1\gt a_2\gt\dots\gt a_k=1$ with $k=\ell(n)$; by Section 2, $a_{k-1}=2$. The terms $a_2,\dots,a_{k-1}$ are totients of numbers that are at least $3$, so they are even (Section 3). For an even $m$, the $m/2$ even numbers among $1,\dots,m$ share the factor $2$ with $m$, so $\varphi(m)\le m/2$. Each step from $a_2$ down to $a_{k-1}$ therefore at least halves the number, so $2=a_{k-1}\le a_2/2^{k-3}$ and $2^{k-2}\le a_2=\varphi(n)\le n-1$.

Up to $4\cdot10^7$ the bound is $2+\log_2(4\cdot10^7-1)\approx27.25$, so every chain has length at most $27$ and its length fits in one byte; length $27$ does occur, first at the prime $35\,946\,497$. A prime with chain length $25$ satisfies $2^{23}\le p-1$, so $p\ge8\,388\,609$; the smallest such prime is $9\,548\,417$. Equality in the claim needs $\varphi(n)=n-1$, so that $n$ is prime, and $n-1=2^{k-2}$; it holds exactly for the primes $2^j+1$, as in $17,16,8,4,2,1$.

For $n\ge2$, Pillai's bounds of 1929 read in our notation ^[3]

$$\log_3\frac n2+2\le\ell(n)\le\log_2 n+2.$$

So for $L\ge2$ a chain of length $L$ starts at a number of at most $2\cdot3^{L-2}$, and this number does have a chain of length $L$: removing one factor $3$ at each step leads from $2\cdot3^{L-2}$ to $2$ and then to $1$. For $L=4$ the limit is $18$, which is why the eight chains of the statement are all the chains of length $4$.

7. Worked example: the two checkpoints

Below $1000$ the primes with chain length $4$ are $5$ and $7$, with sum $12$, as in the statement. Those with chain length $5$ are $11$, $13$ and $19$, with sum $43$; the chain of $13$ is $13,12,4,2,1$. The remaining primes up to $2\cdot3^3=54$ have other lengths: $2$ and $3$ have lengths $2$ and $3$, the primes $17$, $23$, $29$, $31$, $37$ and $43$ length $6$, and $41$, $47$ and $53$ length $7$; by Section 6 no larger prime has length $5$. The C++ program checks both sums before the main computation.

8. Chain lengths count factors of two

Replace every odd prime factor $p$ of a number by the prime factors of $p-1$, and repeat until only factors $2$ are left; this ends, because $p-1$ has only smaller prime factors. For $45=3^2\cdot5$ each factor $3$ turns into one $2$ and the factor $5$ into $2^2$, which leaves $2^4$: four factors $2$, although $45$ is odd. Let $D(n)$ be the number of factors $2$ left at the end. Then $D(1)=0$, $D(2)=1$, $D(p)=D(p-1)$ for every odd prime $p$ and $D(ab)=D(a)+D(b)$, so for $n=2^a p_1^{e_1}\cdots p_r^{e_r}$ with distinct odd primes $p_i$

$$D(n)=a+\sum_{i=1}^{r}e_i\,D(p_i).$$

Claim. $\ell(n)=D(n)+1$ if $n=1$ or $n$ is even, and $\ell(n)=D(n)+2$ if $n\ge3$ is odd.

Proof. For an odd $m=p_1^{e_1}\cdots p_r^{e_r}$ the product formula gives $\varphi(m)=\prod_i p_i^{e_i-1}(p_i-1)$, and because $D(p_i-1)=D(p_i)$,

$$\begin{aligned}D\bigl(\varphi(m)\bigr)&=\sum_{i=1}^{r}(e_i-1)\,D(p_i)\\&\quad+\sum_{i=1}^{r}D(p_i-1)\\&=\sum_{i=1}^{r}e_i\,D(p_i)=D(m).\end{aligned}$$

For an even $n=2^am$ with $a\ge1$ and odd $m$ we have $\varphi(n)=2^{a-1}\varphi(m)$, so $D(\varphi(n))=a-1+D(m)$${}=D(n)-1$. Now take an even $n$. By Section 6 all terms of its chain before the final $1$ are even, so $D$ falls by exactly $1$ at every step, from $D(n)$ down to $D(1)=0$, and the chain has $D(n)+1$ terms. An odd $n\ge3$ first moves to the even number $\varphi(n)$ with the same value of $D$, which adds one term.

Along the chain $45,24,8,4,2,1$, which has $D(45)+2=6$ terms, $D$ takes the values $4,4,3,2,1,0$. The step from $24=2^3\cdot3$ to $8=2^3$ removes one factor $2$ and turns the $3$ into the factor $2$ that it stood for, so the power of $2$ stays $2^3$ while $D$ falls by $1$: $D$ counts the factors $2$ present and still to come. For a prime $p$ the claim reads $\ell(p)=D(p-1)+2$; for $41$ it gives $D(40)+2=3+D(5)+2=7$. The formula goes back to Shapiro in 1943, ^[7] and $D$ is the sequence A064415 of the OEIS. ^[8] Since it needs no totients, it serves as an independent check below.

How the Code Works

The C++ program ^[9] takes the defaults limit $=40\,000\,000$ and target_length $=25$ and the flag run_checkpoints from the struct Options. parse_arguments accepts --limit=, --target-length= and --skip-checkpoints and rejects, with exit code $1$, any other argument, a bound below $2$ and a length below $1$. Its helper parse_int_after_prefix reads the digits into an int without an overflow check, and the vectors have limit + 1 entries, so values near the largest int are not supported. run_checkpoints compares solve(100, 4) with $12$ and solve(1000, 5) with $43$, the sums of Section 7 (exit code $2$ on a mismatch), and main then prints solve(limit, target_length).

solve runs three loops. The first is the linear sieve of Section 5 on a byte vector is_composite, an int vector phi and a vector primes. The product $i\cdot p$ is formed as a 64-bit integer, so its comparison with limit cannot overflow, and a new totient satisfies $\varphi(ip)\le ip\le$ limit, so it fits in an int. The branch (i % p) == 0 applies the first rule of Section 4 and leaves the loop; the other branch applies the second rule. The second loop fills the byte vector chain with chain[1] = 1 and chain[n] = chain[phi[n]] + 1, the rule of Section 2; one byte suffices by Section 6. The third loop adds every prime whose entry equals the target length to an unsigned 64-bit sum, which cannot overflow: even the sum of all integers up to $4\cdot10^7$ is about $8\cdot10^{14}\lt2^{63}$. The sieve includes limit itself, so solve adds the primes $p\le$ limit; for the default bound, which is even, this is the same as $p\lt40\,000\,000$.

The Python and Java programs run the same three loops with fixed parameters and without checkpoints. Python uses a bytearray for the composite flags and for the chain lengths, lists for phi and primes, and its unbounded integers. Java uses boolean[] isComposite, int[] phi, the long product (long) i * primes[j], a byte[] chain, whose signed bytes hold lengths up to $127$, and a long sum. It stores the primes in an int array of fixed length limit / 8, that is $5\,000\,000$, with the counter pc, which is enough for the $2\,433\,654$ primes.

Complexity and Verification

For $N=4\cdot10^7$ the sieve marks each of the $37\,566\,345$ composites once and stops $26\,796\,225$ times because $ip\gt N$, so its inner loop runs $64\,362\,570$ times, about $1.6$ times per number. With the chain pass and the final pass over the $2\,433\,654$ primes, the running time is $O(N)$. The memory is $O(N)$ too: C++ and Java keep $1+4+1$ bytes per number for the flag, the totient and the chain length, about $240$ MB, plus the primes, while Python's list of totients holds a reference and an integer object for most entries. Measured on a current desktop computer (C++ with -O2, OpenJDK 17, CPython 3.11), the wall-clock times were about $0.1$ s, $0.2$ s and $7$ s and the peak resident memory $252$ MB, $307$ MB and $1.8$ GB for C++, Java and Python.

For this article we also ran checks that are not part of the published solutions. The totients and chain lengths of the linear sieve agree with the definition, by counting and by following each chain step by step, for every $n\le2000$, and its totients agree with a factorisation by trial division for every $n\le10^6$. Every composite up to $4\cdot10^7$ is marked exactly once. For the $12$ bounds $2$, $3$, $10$, $50$, $100$, $101$, $997$, $1000$, $5000$, $65537$, $10^5$ and $10^6$ and every target length from $1$ to $21$, the C++ program agrees in all $252$ cases with a computation that starts from $\varphi(m)=m$ and replaces $\varphi(m)$ by $\varphi(m)-\varphi(m)/p$ for every prime $p$ and every multiple $m$ of $p$. For every $n\lt4\cdot10^7$ the chain lengths agree with the formula of Section 8, evaluated without any totient. Finally, the three programs and a separate program that uses only that formula give the same sum.

Footnotes and References

The references below supply the background facts used above. The totient rules of the sieve, the bound of Section 6 and the proof of Section 8 are derived in this article.

Project Euler 214 — Totient Chains. The official statement defines φ(n), shows the chain 5, 4, 2, 1, lists all eight chains of length 4, of which the two that start with a prime have the sum 12, and asks for the sum of all primes less than 40000000 that generate a chain of length 25.
Wikipedia — Dynamic programming. A problem is broken down into simpler subproblems, each solved only once and saved; the bottom-up approach computes the smaller values first and builds the larger ones from them.
OEIS A003434. The number of iterations of φ needed to reach 1, that is ℓ(n) − 1, with the recursion a(n) = a(φ(n)) + 1 for n ≥ 2. The entry states Pillai's bounds log(n/2)/log 3 + 1 ≤ a(n) ≤ log(n)/log 2 + 1 (Bull. Amer. Math. Soc. 35, 1929), which hold for n ≥ 2, and that each value k ≥ 2 occurs for the last time at n = 2·3^(k−1).
Wikipedia — Euler's totient function. Euler's product formula over the distinct primes dividing n, with the remark that inclusion–exclusion on 1, 2, …, n also proves it; multiplicativity for coprime factors; φ(p) = p − 1 for a prime p; and φ(n) even for n ≥ 3.
cp-algorithms — Linear Sieve. Combining each i only with the primes up to its smallest prime factor sets every composite exactly once, by its smallest prime factor, in O(n) total time.
Wikipedia — Sieve of Eratosthenes. The classical sieve takes O(n log log n) operations. Euler's proof of the zeta product formula contains a version that eliminates each composite exactly once, which Gries and Misra (1978) observed to take linear time.
H. S. Bal and G. Bhatnagar — Prime number conjectures from the Shapiro class structure (arXiv:1903.09619). Theorem 1, due to H. Shapiro (Amer. Math. Monthly 50, 1943): for n = 2^α p₁^α₁ ⋯ pᵣ^αᵣ > 1 with distinct odd primes pᵢ, the number of iterations H(n) = ℓ(n) − 1 is α + Σ αᵢ (H(pᵢ) − 1), plus 1 when α = 0. With D(pᵢ) = H(pᵢ) − 1 and D(2) = 1 this is the formula of Section 8.
OEIS A064415. Completely additive, with a(n) = A003434(n) for even n and A003434(n) − 1 for odd n > 1, and described as the exponent of the power of 2 reached from n by repeatedly replacing k with k − k/p for an odd prime p dividing k: the function D.
C++ — Euler214.cpp. The linked immutable C++ revision contains parse_arguments, solve and run_checkpoints. It is the implementation record for this article.

Problem 214 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int limit = 40000000;
    int target_length = 25;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit) ||
            parse_int_after_prefix(arg, "--target-length=", options.target_length)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2 && options.target_length >= 1;
}

u64 solve(const int limit, const int target_length) {
    std::vector<std::uint8_t> is_composite(static_cast<std::size_t>(limit + 1), 0);
    std::vector<int> phi(static_cast<std::size_t>(limit + 1), 0);
    std::vector<int> primes;
    primes.reserve(static_cast<std::size_t>(limit / 10));

    phi[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (!is_composite[static_cast<std::size_t>(i)]) {
            primes.push_back(i);
            phi[static_cast<std::size_t>(i)] = i - 1;
        }

        for (int p : primes) {
            const std::int64_t v = static_cast<std::int64_t>(i) * p;
            if (v > limit) {
                break;
            }

            is_composite[static_cast<std::size_t>(v)] = 1;
            if ((i % p) == 0) {
                phi[static_cast<std::size_t>(v)] = phi[static_cast<std::size_t>(i)] * p;
                break;
            }
            phi[static_cast<std::size_t>(v)] = phi[static_cast<std::size_t>(i)] * (p - 1);
        }
    }

    std::vector<std::uint8_t> chain(static_cast<std::size_t>(limit + 1), 0);
    chain[1] = 1;
    for (int n = 2; n <= limit; ++n) {
        chain[static_cast<std::size_t>(n)] = static_cast<std::uint8_t>(chain[static_cast<std::size_t>(phi[static_cast<std::size_t>(n)])] + 1);
    }

    u64 sum = 0;
    for (int p : primes) {
        if (chain[static_cast<std::size_t>(p)] == target_length) {
            sum += static_cast<u64>(p);
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(100, 4) != 12ULL) {
        std::cerr << "Checkpoint failed for limit=100,target=4" << '\n';
        return false;
    }
    if (solve(1000, 5) != 43ULL) {
        std::cerr << "Checkpoint failed for limit=1000,target=5" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit, options.target_length) << '\n';
    return 0;
}

Python

# Problem 214: Totient Chains
# Sum of primes p < 40,000,000 where the totient chain length is exactly 25.
# Chain: n -> phi(n) -> phi(phi(n)) -> ... -> 1

def solve():
    limit = 40000000
    target = 25

    # Linear sieve to compute phi and find primes
    is_composite = bytearray(limit + 1)
    phi = [0] * (limit + 1)
    primes = []
    phi[1] = 1

    for i in range(2, limit + 1):
        if not is_composite[i]:
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            if i * p > limit:
                break
            is_composite[i * p] = 1
            if i % p == 0:
                phi[i * p] = phi[i] * p
                break
            phi[i * p] = phi[i] * (p - 1)

    # Compute chain lengths
    chain = bytearray(limit + 1)
    chain[1] = 1
    for n in range(2, limit + 1):
        chain[n] = chain[phi[n]] + 1

    total = sum(p for p in primes if chain[p] == target)
    print(total)

solve()

Java

public class Euler214 {
    public static void main(String[] args) {
        int limit = 40000000, target = 25;
        boolean[] isComposite = new boolean[limit + 1];
        int[] phi = new int[limit + 1];
        int[] primes = new int[limit / 8];
        int pc = 0;
        phi[1] = 1;
        for (int i = 2; i <= limit; i++) {
            if (!isComposite[i]) {
                primes[pc++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; j < pc; j++) {
                long v = (long) i * primes[j];
                if (v > limit)
                    break;
                isComposite[(int) v] = true;
                if (i % primes[j] == 0) {
                    phi[(int) v] = phi[i] * primes[j];
                    break;
                }
                phi[(int) v] = phi[i] * (primes[j] - 1);
            }
        }
        byte[] chain = new byte[limit + 1];
        chain[1] = 1;
        for (int n = 2; n <= limit; n++)
            chain[n] = (byte) (chain[phi[n]] + 1);
        long sum = 0;
        for (int j = 0; j < pc; j++)
            if (chain[primes[j]] == target)
                sum += primes[j];
        System.out.println(sum);
    }
}