0%

Problem 74


Problem 74


Digit factorial chains

The number $145$ is well known for the property that the sum of the factorial of its digits is equal to $145$:

$$1! + 4! + 5! = 1 + 24 + 120 = 145$$

Perhaps less well known is $169$, in that it produces the longest chain of numbers that link back to $169$; it turns out that there are only three such loops that exist:

$$\begin{aligned}
&169 \rightarrow 363601 \rightarrow 1454 \rightarrow 169\\
&871 \rightarrow 45361 \rightarrow 871\\
&872 \rightarrow 45362 \rightarrow 872\\
\end{aligned}$$

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

$$\begin{aligned}
&69 \rightarrow 363600 \rightarrow 1454 \rightarrow 169 \rightarrow 363601 (\rightarrow 1454)\\
&78 \rightarrow 45360 \rightarrow 871 \rightarrow 45361 (\rightarrow 871)\\
&540 \rightarrow 145 (\rightarrow 145)\\
\end{aligned}$$

Starting with $69$ produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?


数字阶乘链

众所周知,$145$的各位数字的阶乘之和恰好等于本身:

$$1! + 4! + 5! = 1 + 24 + 120 = 145$$

但很少有人注意到,从$169$开始不断地取各位数字的阶乘之和,将会进入循环回到$169$,而且这是所有循环中最长的一个。事实上,只存在三个这样的循环:

$$\begin{aligned}
&169 \rightarrow 363601 \rightarrow 1454 \rightarrow 169\\
&871 \rightarrow 45361 \rightarrow 871\\
&872 \rightarrow 45362 \rightarrow 872\\
\end{aligned}$$

不难证明,从任意数字出发最终都会陷入循环。例如,

$$\begin{aligned}
&69 \rightarrow 363600 \rightarrow 1454 \rightarrow 169 \rightarrow 363601 (\rightarrow 1454)\\
&78 \rightarrow 45360 \rightarrow 871 \rightarrow 45361 (\rightarrow 871)\\
&540 \rightarrow 145 (\rightarrow 145)\\
\end{aligned}$$

从$69$开始直到进入循环,会得到五个不同的项,而从任意一个小于一百万的数开始,最多能够得到六十个不同的项。

有多少个小于一百万的数满足,从这些数开始不断地取各位数字的阶乘之和,恰好能够得到六十个不同的项?