从单位区间$(0,1)$中取一个小数$0.p_1p_2p_3\ldots$，将其小数部分看作一无穷序列$p=p_1p_2p_3\ldots$。

给定d位的正整数n，记k是n在p中第一次出现时的位置。

例如，取$n=535$，那么：

若$p=31415926535897\ldots$，则$k=9$。

若$p=355287143650049560000490848764084685354\ldots$，则$k=36$。

（注：若p中不包含n，则$k=\infty$）

现取单位区间$(0,1)$上的均匀分布，并记g(n)为此时k的期望值。可以证明，g(n)总是有限的且总是整数，例如$g(535)=1008$。

已知$\sum^{999}_{n=2}g(\lfloor \frac{10^6}{n} \rfloor)=27280188$，求$\sum^{999999}_{n=2}g(\lfloor \frac{10^{16}}{n} \rfloor)$。

注：原题的题面不严谨，此处按题意作了修订。

本题难度:

解答

通过简单模拟也可以观察出以下规律： $$g(n)=1-m+10^m+\sum_{i=1}^{m-1}\chi(i)10^i$$ 其中m是n的长度，$\chi(i)$在n的前i位与后i位相同时取1，否则为0。

汇总计算即得结果$542934735751917735$。

注：本题的严格证明需要一些鞅理论，有些网友指出在《具体数学》（Concrete Mathematics，作者：R.Graham, D.Knuth, O.Patashnik）一书中有本题解法。

r=0
for n in range(2,1000000):
    s=str((10**16)/n)
    m=len(s)
    r+=1-m+10**m+sum(10**i for i in range(1,m) if s[:i]==s[-i:])
print r