因p与10互质,因此显然$f_{m_p}(n)$与$10f_{m_p}(n)=10a+10m_pb$对于p的整除性相同。
此处可以作更强的构造:存在$m_p$,使得$10f_{m_p}(n)$和n模p同余,即
$$10f_{m_p}(n)-n=10bm_p-b=(10m_p-1)b=0 \pmod p,$$
亦即
$$10m_p=1\pmod p$$
由费马小定理可得
$$m_p=10^{p-2} \bmod p$$
就是满足要求的数。
先用筛法找出满足要求的素数,直接用内建函数计算$m_p$汇总即得结果$1601912348822$。
target=10000000
d=[0]*target
n=2
while n < target:
for i in range(n*n,target,n):
d[i]=d[i]+1
n=n+1
while n < target and d[n]>0:
n=n+1
print 39517+sum(pow(10,k-2,k) for k in range(1001,target) if d[k]==0)
|