214 : トーシェント鎖

$\varphi$ をオイラーのトーシェント関数とする。つまり自然数 $n$ に対して $\varphi(n)$ を $\gcd(k,n) = 1$ を満たす $k\ (1 ≤ k ≤ n)$ の数とする。

繰り返し $\varphi$ を適用することで、正の整数は段々値が減っていき、最後は $1$ となる鎖を作る。 例えば $5$ から始めると $5,4,2,1$ という数列ができる。 長さ $4$ の数列を全て以下に列挙する。

$$\begin{aligned} 5,4,2,1 \\ 7,6,2,1 \\ 8,4,2,1 \\ 9,6,2,1 \\ 10,4,2,1 \\ 12,4,2,1 \\ 14,6,2,1 \\ 18,6,2,1 \end{aligned}$$

このうち素数から始まるのは$2$つだけであり、合計は $12$ である。

$40,000,000$ 未満の素数で長さ $25$ の数列を作るもの全ての合計を求めよ。