Problem 214 「トーティエント鎖」 †

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

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

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

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

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

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2009-02-28 (土) 12:07:15