Project Euler 717

题目

Summation of a Modular Formula

For an odd prime \(p\), define \(f(p) = \left\lfloor\frac{2^{(2^p)}}{p}\right\rfloor\bmod{2^p}\)

For example, when \(p=3\), \(\lfloor 2^8/3\rfloor = 85 \equiv 5 \pmod 8\) and so \(f(3) = 5\).

Further define \(g(p) = f(p)\bmod p\). 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)\)

解决方案

本题参考了Thread中的一些解法。

令\(r=2^{2^p}\%p\)，那么有\(f(p)\equiv\dfrac{2^{2^p}-r}{p}\equiv-\dfrac{r}{p}\pmod {2^p}\).

注意到\(i_p=\dfrac{(p-1)/2\cdot 2^p+1}{p}=\dfrac{(p-1)\cdot 2^{p-1}+1}{p}\)是一个整数，且\(p\cdot i_p\equiv1\pmod{2^p}\)成立。因此\(i_p\)确实是\(p\)在模\(2^p\)上的逆元。

那么就有\(f(p)=-r\cdot\dfrac{(p-1)\cdot 2^{p-1}+1}{p}\% 2^p\)。这个数相当于是找一个最小的整数\(k\)，使得\(k\cdot 2^p-r\cdot\dfrac{(p-1)\cdot 2^{p-1}+1}{p}\ge 0\)成立。即可有\(k\ge\dfrac{r(p-1)}{2p}+\dfrac{r}{p\cdot 2^p}\)。由于第二个项的分母为\(p\cdot 2^p\)，数量级远远小于第一个项。因此仅需表明\(k>\dfrac{r(p-1)}{2p}\)即可。也就是有\(k=\left\lfloor\dfrac{r(p-1)}{2p}\right\rfloor+1\)。

接下来是计算\(\dfrac{(p-1)\cdot 2^{p-1}+1}{p}\%p\)的值，其值等于\(\dfrac{((p-1)\cdot 2^{p-1}+1)\% p^2}{p}\)。

因此最终有

\(\begin{aligned} f(p)\%p&=\left(k\cdot 2^p-r\cdot\dfrac{((p-1)\cdot2^{p-1}+1)\%p^2}{p}\right)\%p\\ &=\left(2k-r\cdot\dfrac{((p-1)\cdot2^{p-1}+1)\%p^2}{p}\right)\%p\\ \end{aligned}\)

代码

from tools import get_prime

N = 10 ** 7
pr = get_prime(3, N)
ans = 0
for p in pr:
    r = pow(2, pow(2, p, p - 1), p)
    k = r * (p - 1) // (p + p) + 1
    up = (p - 1) * pow(2, p - 1, p * p) + 1
    x = up % p ** 2 // p
    ans += (2 * k - r * x) % p
print(ans)