Detailed mathematical approach

Problem Summary

For a positive integer \(n\), write its decimal digits as \(d_1,d_2,\dots,d_r\) and define the digit-factorial map

$F(n)=\sum_{i=1}^{r} d_i!.$

Starting from \(n\), we repeatedly apply \(F\). The resulting sequence eventually repeats, so each start produces a finite list of distinct terms followed by a return to a value seen earlier. The problem asks for the number of starting values with \(1 \le n < 10^6\) whose chain contains exactly 60 non-repeating terms.

The classic example is \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\), so the distinct part has length 5. The implementations solve the full count by treating these chains as walks in a finite functional graph and memoizing the exact remaining length of every state they finish.

Mathematical Approach

The central object is not a large search tree but a deterministic map: every integer has exactly one outgoing edge, namely \(n \mapsto F(n)\). That means every trajectory has the same shape: a tail leading into a cycle. The whole problem is therefore to compute, for each start below one million, how many distinct vertices appear before the first repeated one.

The Digit-Factorial Map

The ten digit factorials are fixed once and for all:

$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$

So evaluating \(F(n)\) is just decimal digit extraction plus table lookup. Zeros matter: every zero digit contributes \(0!=1\), which is why numbers such as \(363600\) jump to \(1454\) rather than to a smaller value.

Why Repetition Is Guaranteed

If \(1 \le n < 10^6\), then \(n\) has at most six digits, so its first image satisfies

$F(n)\le 6\cdot 9! = 2{,}177{,}280.$

After that, every term has at most seven digits, and therefore every later image satisfies

$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$

Thus every chain starting below one million enters the finite set \(\{1,2,\dots,2{,}540{,}160\}\) immediately and never leaves it. A deterministic walk inside a finite set must eventually revisit a value, so every chain has a well-defined tail and cycle.

Tail, Cycle, and Exact Chain Length

For a starting value \(n\), write

$a_0=n,\qquad a_{k+1}=F(a_k).$

The chain length required by the problem is the number of distinct values before the first repetition:

$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$

Suppose a fresh exploration sees distinct values \(a_0,a_1,\dots,a_{t-1}\) and then finds that the next value equals \(a_r\) for some \(0\le r<t\). Then \(a_r,a_{r+1},\dots,a_{t-1}\) form a cycle of length

$c=t-r.$

Every point already on that cycle has exactly \(c\) non-repeating terms ahead of it, while each point in the tail has to traverse the remaining tail plus the full cycle. Therefore

$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$

These formulas are exactly what the implementations write into the memo table when a new cycle is discovered.

Reusing a Solved Suffix

Often a new search does not have to discover a brand-new cycle. Instead it reaches a value whose chain length was already computed earlier. If the first known value is \(a_t=m\) and \(\ell(m)\) is already stored, then the current path \(a_0,\dots,a_{t-1}\) is still repetition-free; otherwise the walk would have terminated earlier. So each earlier point simply adds one extra step:

$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$

This recurrence is the key optimization. Many starting values flow into the same suffix, so once that suffix is solved once, every later chain can stop immediately when it reaches it.

Worked Examples: 69 and 78

For \(69\), the chain is

$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$

Here the distinct segment is \((69,363600,1454,169,363601)\), and the next value repeats the entry at position \(r=2\). Thus \(t=5\), the cycle length is \(c=3\), and the formulas give

$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$

A second useful checkpoint is

$78 \to 45360 \to 871 \to 45361 \to 871.$

Now the repeat begins at \(r=2\) with \(t=4\), so \(c=2\). Hence

$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$

These two examples show both ingredients of the method: detect where the cycle begins, then propagate exact lengths backward through the tail.

How the Code Works

Precomputing the digit factorials

The C++, Python, and Java implementations all begin by storing the ten values \(0!,1!,\dots,9!\). That makes each application of \(F\) a short digit loop with constant-time table lookups instead of repeated factorial computation.

Resolving one starting value

To evaluate a single chain, the implementation keeps two temporary structures for the current exploration: an ordered list of newly visited values and a hash structure recording where each of those values first appeared. At each step it computes the next value and checks two termination conditions.

If the new value already has a memoized length, the implementation walks backward through the ordered list and assigns lengths using \(\ell(a_i)=\ell(m)+t-i\). If the new value already appeared on the current path, the ordered list is split into tail and cycle, the cycle nodes receive the common cycle length, and the tail nodes receive increasing lengths as one moves backward. In both cases, once these memo entries are written, the length of the original start is immediately known.

Scanning all starts below one million

The outer loop runs through every \(n\) with \(1 \le n < 10^6\), asks for \(\ell(n)\), and increments the answer when \(\ell(n)=60\). Because the memo table is shared across the entire sweep, many later starts terminate after only a few steps. The C++ and Python implementations also include small built-in checkpoints for the sample lengths \(69 \mapsto 5\) and \(78 \mapsto 4\) before performing the full count.

Complexity Analysis

Once a chain enters the bounded region, every evaluation of \(F\) reads at most seven digits, so each transition is \(O(1)\) in practice. Let \(U\) be the number of distinct values that are actually discovered while processing all starts below one million. Because a value is fully expanded only the first time it is solved, the total work is \(O(10^6 + U)\) hash-table operations, or \(O((10^6+U)d)\) digit operations with \(d\le 7\).

The bound above gives \(U\le 2{,}540{,}160\), so the algorithm is effectively linear in a few million states. Memory usage is \(O(U)\) for the memoized chain lengths, plus temporary storage proportional to the length of the chain currently being explored.

Footnotes and References

1. Problem page: Project Euler 74
2. Factorial: Wikipedia - Factorial
3. Factorion: Wikipedia - Factorion
4. Memoization: Wikipedia - Memoization
5. Functional graph: Wikipedia - Functional graph
6. Cycle detection: Wikipedia - Cycle detection