---

Problem 717

---

Summation of a Modular Formula

For an odd prime $p$, define $f(p)=\lfloor \frac{2^{(2^p)}}{p}\rfloor mod{2}^p$.
For example, when $p=3$, $\lfloor 2^8/3\rfloor =85\equiv 5(\mathrm{mod}8)$ and so $f(3)=5$.

Further define $g(p)=f(p)modp$. You are given $g(31)=17$.

Now define $G(N)$ to be the summation of $g(p)$ for all odd primes less than $N$.
You are given $G(100)=474$ and $G({10}^4)=2819236$.

Find $G({10}^7)$.

---

余数求和

对于奇素数$p$，记$f(p)=\lfloor \frac{2^{(2^p)}}{p}\rfloor mod{2}^p$。
例如，若$p=3$，$\lfloor 2^8/3\rfloor =85\equiv 5(\mathrm{mod}8)$，因此$f(3)=5$。

记$g(p)=f(p)modp$。已知$g(31)=17$。

记$G(N)$为所有小于$N$的奇素数$p$所对应$g(p)$之和。
已知$G(100)=474$，$G({10}^4)=2819236$。

求$G({10}^7)$。

---