通过尝试可以得出这样的经验公式
$$M(2^k+1)=4^k+2^{k+1}-3^k,$$
从而有
$$\sum_{k=0}^{10^{18}}M(2^k+1)=\frac{4^{10^{18}+1}-1}{4-1}+2\cdot\frac{2^{10^{18}+1}-1}{2-1}-\frac{3^{10^{18}+1}-1}{3-1}.$$
由于2,3,4都和7互素，因此若记$\varphi$为欧拉Totient函数，那么
$$a^{\varphi(m)}=1\pmod m$$
以及
$$a^{-1}=a^{\varphi(m)-1} \pmod m$$
对$a=2,3,4$和$m=7^9$都成立。容易计算$\phi(m)=6\cdot 7^8=34588806$，代入即得最终结果$5032316$。
注：为便于用标准库函数作快速幂，以下代码为Python 3。
m=40353607
p=34588806
a=pow(10,18,p)+1
print(((pow(4,a,m)-1)*pow(3,p-1,m)+2*(pow(2,a,m)-1)-(pow(3,a,m)-1)*pow(2,p-1,m))%m)
|
