Solution

Answer: 402

Define the digit-factorial map

$$f(n)=\sum_{\text{digits }d\text{ of }n} d!$$

and repeatedly apply $f$:

$$n,\ f(n),\ f(f(n)),\dots$$

We are asked:

for every starting number $n<10^6$,
count the number of distinct terms before repetition,
and determine how many such chains have length exactly $60$.

Mathematical analysis

1. Bounding the search

The key observation is that factorials of digits grow quickly, but there are only finitely many possible next values.

The largest factorial digit contribution is

$$9! = 362880.$$

A number below one million has at most $6$ digits, so

$$f(n)\le 6\cdot 9! = 2177280.$$

Even if we later reach a 7-digit number, the maximum possible value is

$$7\cdot 9! = 2540160.$$

So every chain rapidly enters the finite set

$${1,2,\dots,2540160}.$$

Therefore every sequence must eventually repeat and enter a loop.

2. Known loops

The problem already gives the only loops:

Length 3 loop

$$169 \to 363601 \to 1454 \to 169$$

Length 2 loops

$$871 \leftrightarrow 45361$$

$$872 \leftrightarrow 45362$$

Length 1 loops

$$1,\ 2,\ 145,\ 40585$$

Any starting number eventually falls into one of these cycles.

3. Computing chain lengths efficiently

A naive approach:

for each $n<10^6$,
generate the sequence until repetition,
count distinct terms.

This works, but we can optimize heavily with memoization.

Suppose we visit numbers

$$n_0,n_1,n_2,\dots$$

and encounter a repeated term.

If a loop begins at position $k$, then:

chain length of $n_k$ is the loop size,
chain length of $n_{k-1}$ is loop size $+1$,
etc.

We can cache already-computed lengths.

4. Fast digit-factorial evaluation

Precompute:

$$0!,1!,2!,\dots,9!$$

Then for each number:

sum_fact = sum(fact[int(d)] for d in str(n))

This makes transitions extremely fast.

Python implementation

# Precompute factorials of digits 0-9
fact = [1] * 10
for i in range(2, 10):
    fact[i] = fact[i - 1] * i

def next_term(n):
    """Return sum of factorials of digits of n."""
    total = 0
    while n > 0:
        n, d = divmod(n, 10)
        total += fact[d]
    return total

# Memoized chain lengths
chain_len = {}

TARGET = 60
LIMIT = 1_000_000

count = 0

for start in range(1, LIMIT):

    seen = {}
    sequence = []

    n = start

    while True:

        # If already known, propagate lengths backward
        if n in chain_len:
            known = chain_len[n]

            # Assign lengths backwards
            for i in range(len(sequence) - 1, -1, -1):
                known += 1
                chain_len[sequence[i]] = known

            total_length = chain_len[start]
            break

        # Loop detected inside current sequence
        if n in seen:
            loop_start = seen[n]
            loop_length = len(sequence) - loop_start

            # Assign loop members
            for i in range(loop_start, len(sequence)):
                chain_len[sequence[i]] = loop_length

            # Assign pre-loop members backwards
            length = loop_length
            for i in range(loop_start - 1, -1, -1):
                length += 1
                chain_len[sequence[i]] = length

            total_length = chain_len[start]
            break

        seen[n] = len(sequence)
        sequence.append(n)

        n = next_term(n)

    if total_length == TARGET:
        count += 1

print(count)

Code walkthrough

Factorial precomputation

fact = [1] * 10
for i in range(2, 10):
    fact[i] = fact[i - 1] * i

Stores:

$$[1,1,2,6,24,120,720,5040,40320,362880]$$

so factorial lookup is $O(1)$.

Transition function

def next_term(n):

Computes

$$f(n)=\sum d!$$

using repeated digit extraction with divmod.

Example:

For $69$,

$$6!+9!=720+362880=363600.$$

Detecting loops

We maintain:

seen = {}
sequence = []

Example for $69$:

69
363600
1454
169
363601
1454  <-- repeat

The repeat identifies the loop.

The chain has 5 non-repeating terms.

Memoization

If we already know the chain length of a number encountered later, we reuse it immediately.

This dramatically reduces runtime because many chains merge together.

Small-example verification

For the example:

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

before repetition, there are exactly:

$$5$$

distinct terms.

The program reproduces this.

Similarly:

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

has length $4$.

Final verification

We are counting starting numbers below one million whose non-repeating chain length is exactly $60$.

Important checks:

The maximum chain length stated in the problem is $60$.
Our algorithm explicitly measures non-repeating terms.
Memoization guarantees correctness and efficiency.
This is the known Project Euler result.

Therefore the computed total is:

$$402$$

Answer: 402

Project Euler Problem 74