幂尾数

给定整数n，令$x=f(n)$为小于$10^9$且$n^x$的最后9位数字（不满9位时可以添加前导0补满9位）恰等于x本身的最大的数x。若不存在这样的数，则定义$f(n)=0$。

例如 \begin{align*} f(4)&=411728896 \quad (4^{411728896}=\ldots 490411728896) \\ f(10)&=0 \\ f(157)&=743757 \quad (157^{743757}=\ldots 567000743757) \\ \end{align*} 可以验证$\sum_{n=2}^{1000}f(n)=442530011399$，求$\sum_{n=2}^{10^6}f(n)$。

本题难度:

解答

当n不能被10整除时，以$x_0=n$初值，$x\mapsto n^x\bmod 10^9$似乎很快就会收敛到一个不动点，该点也是题设中要求的数。

当n能被10整除时$n^n模10^9$得0，此时似乎也有$f(n)=0$。

具体原因未加验证，不过按以上方法试算已可得正确的最终结果$450186511399999$。

注：为使用内建函数pow作快速幂，以下代码为Python 3，代码中还打印了进度信息。

mod=10**9

s=0
for n in range(2,10**6+1):
    if n%10>0:
        x=n
        y=pow(n,x,mod)
        k=0
        while x!=y:
            x=y
            y=pow(n,x,mod)
        s+=x
    if n%10000==0:
        print(n//10000,"percent completed, current sum:",s)

print(s)