问题
数字145因为它的每位的阶乘之和就是它本身而闻名：
1! + 4! + 5! = 1 + 24 + 120 = 145
可能169没那么出名，但是它可以按照这个规则产生一条最终还是会变回169的链；下面有三个数字都可以产生这样的循环链：
169 → 363601 → 1454 → 169 871 → 45361 → 871 872 → 45362 → 872
不难证明，所有数字按照这个规则生成的链都会最终卡在一个循环当中。例如：
69 → 363600 → 1454 → 169 → 363601 (→ 1454) 78 → 45360 → 871 → 45361 (→ 871) 540 → 145 (→ 145)
从69开始的链有5个数字不在循环当中，然而，在开始数字小于1000,000的情况下，链的数字不在循环当中最多有60个。
那请问，当始数字小于1000,000，有多少条链的数字不在循环当中刚好长达60？
* 传送门
分析
貌似没什么可以分析的……顺藤摸瓜，直接暴力解题吧……
答案
这个暴力解题当然可以得到答案，但是耗时超过1分钟。
// answer: brute force
const start = Date.now()
const factorial = [1]
for (let i = 1; i < 10; ++i)
factorial[i] = factorial[i-1]*i
function digit_factorial_sum(n) {
let sum = 0
for (; n > 0; n = Math.floor(n/10))
sum += factorial[n%10]
return sum
}
function chain_non_repeating_len(n) {
let non_repeating_len = 0
const chain = {}
while (!(n in chain)) {
chain[n] = n
non_repeating_len++
n = digit_factorial_sum(n)
}
return non_repeating_len
}
let result = 0
for (let n = 1; n < 1000000; ++n)
if (chain_non_repeating_len(n) == 60)
++result
alert(result + ', ' + (Date.now()-start) + 'ms')
得到答案后，逛解题论坛，发现其实还是可以有分析的。
以363600为例，它的数位阶乘之和与363601都是1454，这是因为0! = 1! = 1。也就是说，产生与以363600开头一样的链的数字，只需要看363600的0或1可以替换成多少种方式。显然，363601、363610、363611这三个数字都会产生一样的链。因为363600有2位0或1，所以有\(2^2 = 4\)条相同的链。
而又由于加法适用交换率，所以633600、103636与363600产生的链也是一样的。
也就是说，如果我们知道第一条链不重复长度为60的开头数字，通过排列组合，便可以知道所有链不重复长度为60的开头数字。这种方法是建立在长度为60的链除了开头数字不一样之外、其它都一样这个假设上。所以对于其他长度的链未必有效。
稍微改动代码，就可以在几毫秒内得到第一条不重复长度为60的链的开头数字为1479。所以同为4位数的情况下，同样产生这条链的数字有\(4!=24\)个。而将1换成0后，有效的4位数便有\(4!-3!=18\)个。
而5位数没有不重复链长为60的数字。
到了6位数，最后个满足条件的是974322，再稍微改动代码，1秒左右就可以找到这个数。它没有0或1，所以不需要考虑0! = 1!。其中只有2是重复的，合共有5个不同的数字。所以974322所有排列数字有\(C_6^2 4! = \frac{6!}{2!(6-2)!}\cdot 4! = \frac{6!}{2} = 360\)。
所以答案便是\(24+18+360=402\)。
第一次遇到欧拉计划这种可以通过程序辅助笔算得到答案的题目。
打赏作者