PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 512 / べき乗のトーシェント数の和

オイラーのトーシェント関数を φ(n) とする。

 f(n)=\left(\sum_{i=1}^n \varphi (n^i)\right)\pmod{n+1}

 g(n)=\sum_{i=1}^n f(i)

とすると g(100) = 2007 となる。

g(5*10^8) を求めよ。

Problem 512 - Project Euler


 \varphi(n^i)=n^{i-1} \varphi(n) を使って f(n) の式を整理します。

 \displaystyle\sum_{i=1}^n \varphi (n^i)=\varphi(n)\displaystyle\sum_{i=1}^n n^{i-1}\equiv \varphi(n)\displaystyle\sum_{i=1}^n (-1)^{i-1} \pmod{n+1}

これは n が偶数のとき 0,奇数のとき φ(n) です。奇数について φ(n) の和を求めます。5分かかりました。