123. 素数平方余数(Prime square remainders)

\(p_n\)是第\(n\)个素数:\(2, 3, 5, 7, 11, \cdots\)并记\(r\)\((p_n-1)^n+(p_n+1)^n\)除以\(p_n^2\)的余数,如\(n=3\)时,\(p_3=5\),则\(4^3+6^3=280\equiv5\ mod\ 25\)。使该余数首次超过\(10^9\)的最小的\(n\)值为\(7037\),求使得该余数首次超过\(10^{10}\)的最小\(n\)值。

分析:这道题和我们之前已经分析过的第一百二十题基本一样,实际上还要更为简单一些。采用类似的推理,易知\((p_n-1)^n+(p_n+1)^n\)除以\(p_n^2\)的余数\(r\)\(n\)为偶数时恒为二,而在\(n\)为奇数等于\(2np_n\),因此要求余数首次超过\(10^{10}\)\(n\)的最小值,\(n\)必然为一个奇数。我们可从第\(7037\)个素数开始向上搜索,跳过所有偶数位的素数,计算\(2np_n\),当其大于\(10^{10}\)时返回\(n\)即为题目所求,代码如下:

# time cost = 358 ms ± 3.45 ms

from sympy import nextprime

def main(N=10**10):
    n,p = 7037,71059
    while True:
        np = nextprime(p,2)
        n = n + 2
        r = 2*n*np
        if r > N:
            return n
        else:
            p = np