同余逆

共有八个小于15且与15互素的正整数：1，2，4，7，8，11，13，14。

这些数在模15意义下的乘法逆分别是：1, 8, 4, 13, 2, 11, 7, 14： $$1\cdot1=2\cdot8=4\cdot4=7\cdot13=11\cdot11=14\cdot14=1 \pmod{15}.$$ 记$\ell(n)$为小于$n-1$且在模n意义下的乘法逆等于其本身的最大正整数。例如$\ell(15)=11, \ell(100)=51, \ell(7)=1$。

求$\sum_{n=3}^{2\times 10^7}\ell(n)$。

本题难度:

解答

本题用sympy暴力求解即可，需要注意$n-1$的逆总是其本身，所有要在返回的列表中将其排除，最终结果是$153651073760956$。

注：因需使用sympy库，以下代码为Python 3。代码用list comprehension完全可以缩写为两行，不过由于运行时间较长，为了能打印进度而扩展为显式的循环。

from sympy.ntheory import sqrt_mod

#print(sum(max(sqrt_mod(1,n,True)) for n in range(3,2*(10**7)+1)))

s=0
for n in range(3,2*(10**7)+1):
    s+=sorted(sqrt_mod(1,n,True))[-2]
    if n%20000==0:
        print(f"{n/200000:.1f} percent completed, current sum: {s}")

print(s)