PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 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である。

40,000,000未満で長さ 25 の数列を作る素数の総和を求めよ。

Problem 214 - Project Euler


毎度毎度のことですが,Mathematica の組み込み関数にたよって解きました。
NestWhileList で EulerPhi のリストを作って,その長さを計算しています。メモリ(64GB)的にはちょっと厳しく,無事最後まで行けてほっとしました。