问题
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……
打赏作者