1 / 1

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$ である.

$40000000$ 未満で長さ $25$ の数列を作る素数全ての合計を求めよ.

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

\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$ である.

$40000000$ 未満で長さ $25$ の数列を作る素数全ての合計を求めよ.