*[[Problem 214:http://projecteuler.net/problem=214]] 「トーティエント鎖」 [#dbed05ef]

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

繰り返し φ を適用することで, 正の整数は段々値が減っていき, 最後は 1 となる鎖を作る. ~
例えば 5 から始めると, 5,4,2,1 という数列ができる. ~
長さ 4 の数列を全て以下に列挙する.
CENTER:5,4,2,1
CENTER:7,6,2,1
CENTER:8,4,2,1
CENTER:9,6,2,1
CENTER:10,4,2,1
CENTER:12,4,2,1
CENTER:14,6,2,1
CENTER:18,6,2,1

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

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

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS