问题
145是一个有趣的数字，因为 1! + 4! + 5! = 1 + 24 + 120 = 145 。
请找到所有能写成各数位阶乘之和的数字的和。
注意：由于 1! = 1、2! = 2 它们都等于它们自身，不能当作和。
* 传送门
分析
这个问题和《问题30》十分相似。
由于阶乘的运算结果十分容易变得非常大、位数非常多，例如 8! = 40320，已经是5位数，9! = 362880，已经是6位数。我们对所要找的数字的位数进行分析：
- 由于阶乘的值是个位数的情况只有0、1、2、3，显然个位数没有任何能满足条件的解；
- 又由于阶乘的值小于2位数的情况只有0、1、2、3、4，这5个数里面不论如何组合出2位数也没有任何能满足条件的解；
- 如果符合要求的数字是3位数，3*9! = 1088640 已经是7位数，3 < 7，所以有可能存在满足条件的解；
- 如果符合要求的数字是4位数，4*9! = 1451520 也是7位数，4 < 7，所以有可能存在满足条件的解；
- ……（如此类推）……
- 如果符合要求的数字是6位数，6*9! = 2177280 也是7位数，6 < 7，所以有可能存在满足条件的解；
- 如果符合要求的数字是7位数，7*9! = 2540160 也是7位数，7 == 7，所以有可能存在满足条件的解；但是由于 9999999 > 2540160，所以这便约束使得这个7位数应该小于等于7*9!、且尽可能多9的7位数，也就是1999999；
- 如果符合要求的数字是8位数，8*9! = 2903040 也还是7位数，8 > 7，这意味着这个8位数永远不可能和7位数相等，所以不可能存在满足条件的解；
- 由于阶乘是单调递增的，所以后面的情况都不必考虑了。
答案
// answer: brute force
const start = Date.now()
const factorials = [1] // 预先计算0至9的阶乘，后面不必重复计算
for (let i = 1, prod = 1; i < 10; ++i, prod *= i)
factorials.push(prod)
let result = 0
for (let n = 100; n < 1499999; ++n) { // 使用 1499999 作为上界，见下文描述
let sum = 0
for (let num = n; num > 0;) {
const d = num % 10
sum += factorials[d]
num = (num - d) / 10
}
if (n == sum)
result += n
}
alert(result + ', ' + (Date.now() - start) + 'ms')
然而，最后发现能够满足条件的数字只有145和40585…………这和前面找出来的上界值都想去甚远……但是40585却十分接近8!。难道有直接能通过数学分析、笔算就可以得到结果的解题方法？？但是浏览本问题论坛答案后，也没发现有人提出这样的解题方法……
但是却发现了这个和这个……发现只有4个这样的数字……早说嘛……感觉浪费时间了……维基百科的词条还进一步将这个上界推理至1499999……
打赏作者
