0156 数字计数
* * * *
拉格朗日计划
* * * *
数字计数

令$f(n,d)$为$0,1,\ldots,n$这$n+1$个整数的十进制表示中数字d出现的次数,例如$f(0,1)=0$、$f(1,1)=\ldots=f(9,1)=1$、$f(10,1)=2$、$f(11,1)=4$、$f(12,1)=5$。

$f(n,1)$不会等于3,且$f(n,1)=n$的前两个解是$n=0$和$n=1$,第三个解是$n=199981$。

显然只要$d\neq0$,那么$n=0$就是$f(n,d)=n$的第一个解。

记$s(d)$为关于n的方程$f(n,d)=n$的所有解之和。可以验证$s(1)=22786974071$。

求$\sum_{d=1}^9s(d)$。

注意:若n同时是$f(n,d_1)=n$和$f(n,d_2)=n$的解($d_1\neq d_2$),那么按上述规则n在$s(d_1)$和$s(d_2)$中都应被计入。

本题难度:



解答

下表给出了d取不同值时$f(n,d)=n$的具体解:

$d=1$: OEIS A014778

$d=2$: OEIS A101639

$d=3$: OEIS A101640

$d=4$: OEIS A101641

$d=5$: OEIS A130427

$d=6$: OEIS A130428

$d=7$: OEIS A130429

$d=8$: OEIS A130430

$d=9$: OEIS A130431

上述数据中$d=2$到9的情况已汇总整理为该文件,求和即可得结果$21295121502550$。

s=22786974071

with open("156_data.txt") as f:
    for line in f:
        if line[0]!="!":
            s+=int(line.split()[1])

print s