首先注意到任意自然数n都可以写成另一个自然数m各位数字的阶乘和，比如取连续n个1就是一种写法。
记$ds(m)$为m中各位数字的和，$fs(m)$为m中各位数字的阶乘和，则$fs(m)$和$ds(m)$都与m中数字的顺序无关，因此当$fs(m)$一定时，位数越少且同等位数下字典序越小的m越能满足要求。
从而对固定的$n=fs(m)$，构造最小m的方法是找到最大的、满足$k!$不超过n的k，记录n模$k!$的商和余数$q_k,r_k$，再将n更新为$r_k$并重复这一过程直到余数为0（因为$1!=1$，所以最后总能达到余数为0的状态），那么m就等于连续$q_1$个1，连续$q_2$个2。。。连续$q_k$个k相连。
例如$122=1\times 5!+1\cdot 2!$，因此满足$fs(m)=122$的最小m就是1个2后接1个5，即25。
遍历1到$10^7$之间的n，用上述方法计算最小的m并更新$g(ds(n))$，如此可计算出$g(1)$到$g(62)$。而对$i=63$到$i=150$之间的数，m,n增长都非常快，无法继续遍历。
此时可以观察到的规律是例如$i=63,64,65,\ldots$时$fs(m)$分别等于$9999999, 19999999, 29999999,\ldots$，从而有贪心推测
$$fs(m)=(i\bmod 9+1)\cdot (10^{\lfloor i/9\rfloor})-1,$$
这一步是启发式的，缺乏直接的论证，这也是本题的主要难度所在，需要识别出在$i=63$处作分割并归纳出$i\ge63$时的规律。
在实现中还需要将不超过$9!$的结果都作缓存再直接求和（否则在$i\ge63$时所涉及的整数m仍然非常巨大，尝试生成这样的m并根据数位运行仍会十分缓慢）。
最终结果是$8184523820510$（其中前62项的和只有3077）。
注：以下代码中还输出了第一部分（即$i<63$时）遍历中的进度信息。
import math
ds=lambda n:sum(int(d) for d in str(n))
infty=0
target=10000000
bound=math.factorial(9)
cutoff=63
f=[math.factorial(i) for i in range(10)]
c=[infty]*bound
g=[infty]*cutoff
k=1
for n in range(1,target):
while k<9 and f[k+1]<=n:
k+=1
q,r=n/f[k],n%f[k]
m=int(str(k)*q) if r==0 else int(str(c[r])+str(k)*q)
if n<bound:
c[n]=min(c[n],m) if c[n]!=infty else m
s=ds(n)
if s<cutoff:
g[s]=min(g[s],m) if g[s]!=infty else m
if n%1000000==0:print n/1000000,"/10 completed."
print sum(ds(n) for n in g[1:])+sum(9*(n/f[9])+ds(c[n%f[9]]) for n in [(i%9+1)*(10**(i/9))-1 for i in range(63,151)])
|
