---

Problem 512

---

Sums of totients of powers
Let $\varphi (n)$ be Euler’s totient function.

Let $f(n)=({\mathrm{\Sigma }}_{i=1}^n\varphi (n^i))\text{ mod }(n+1)$.

Let $g(n)={\mathrm{\Sigma }}_{i=1}^{n}f(i)$.

$g(100)=2007$.

Find $g(5\times {10}^8)$.

---

幂的欧拉总计函数和

记$\varphi (n)$为欧拉总计函数。

记$f(n)=({\mathrm{\Sigma }}_{i=1}^n\varphi (n^i))\text{ mod }(n+1)$。

记$g(n)={\mathrm{\Sigma }}_{i=1}^{n}f(i)$。

已知$g(100)=2007$。

求$g(5\times {10}^8)$。

---