Problem 74: Digit Factorial Chains

Mathematical Analysis

Definition 1 (Digit Factorial Function)

The digit factorial function $f: \mathbb{N} \to \mathbb{N}$ is defined by:

where $d_0 d_1 \cdots d_k$ is the decimal representation of $n$.

Definition 2 (Chain Length)

The chain length $L(n)$ is the number of distinct elements in the sequence $n, f(n), f^2(n), \ldots$ before the first repetition.

Theorem 1 (Eventual Periodicity)

For all $n \geq 1$, the orbit $(n, f(n), f^2(n), \ldots)$ eventually enters a cycle. Moreover, for any $n < 10^7$, we have $f(n) \leq 2{,}540{,}160$.

Proof. A $k$-digit number $n$ satisfies $n \geq 10^{k-1}$ (for $k \geq 2$) and $f(n) \leq k \cdot 9! = 362880k$. For $k \geq 8$:

Thus $f(n) < n$ for all $n \geq 10^8$, and more generally, $f$ maps any $n$ into $[1, 7 \times 362880] = [1, 2{,}540{,}160]$ within finitely many iterations. Since this is a finite set, the orbit must revisit a value, creating a cycle.

For $n < 10^7$ (at most 7 digits), $f(n) \leq 7 \times 362880 = 2{,}540{,}160$ directly. $\square$

Theorem 2 (Complete Classification of Cycles)

The digit factorial function $f$ has exactly the following cycles:

• Fixed points (1-cycles): $\{1\}$, $\{2\}$, $\{145\}$, $\{40585\}$.
• 2-cycle: $\{871, 45361\}$.
• 3-cycle: $\{169, 363601, 1454\}$.

There are no other cycles.

Proof. Every cycle element $c$ must satisfy $c \leq 2{,}540{,}160$ (since $f$ maps any value in this range back into it, and cycle elements are closed under $f$). The claim is verified by exhaustive computation: iterate $f$ from every starting point in $[1, 2{,}540{,}160]$ and record all cycles encountered.

The fixed points satisfy $f(n) = n$. One verifies:

• $f(1) = 1! = 1$.
• $f(2) = 2! = 2$.
• $f(145) = 1! + 4! + 5! = 1 + 24 + 120 = 145$.
• $f(40585) = 4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = 40585$.

The 2-cycle: $f(871) = 8! + 7! + 1! = 40320 + 5040 + 1 = 45361$; $f(45361) = 24 + 120 + 6 + 720 + 1 = 871$.

The 3-cycle: $f(169) = 1 + 720 + 362880 = 363601$; $f(363601) = 720 + 720 + 6 + 720 + 1 + 1 = ...$ Tracing carefully: $f(363601) = 6 + 720 + 6 + 720 + 1 + 1 = 1454$; $f(1454) = 1 + 24 + 120 + 24 = 169$. $\square$

Lemma (Chain Length Recursion)

If $m = f(n)$ and $n$ is not part of a cycle, then $L(n) = 1 + L(m)$.

Proof. The chain starting at $n$ is $(n, m, f(m), \ldots)$. Since $n$ is not in a cycle, $n \neq f^j(m)$ for all $j \geq 0$, so the number of distinct terms is $1 + L(m)$. $\square$

Corollary (Memoization)

By the Lemma, once $L(m)$ is known for some $m$, the chain length of any predecessor $n$ (with $f(n) = m$ and $n$ not in a cycle) is immediately determined. This enables dynamic programming over the finite state space $[1, 2{,}540{,}160]$.

Editorial

The useful fact here is that many starting values quickly merge into the same tail. Once we know the chain length of some intermediate value, every earlier value that reaches it can inherit that information immediately, so memoization saves almost all repeated work.

For each starting number, we repeatedly apply the digit-factorial map while recording the order in which values appear. There are two ways the walk can stop. If it reaches a value already stored in the cache, then the rest of the chain is already known and we can propagate lengths backward through the current path. If it repeats a value inside the current path, then we have found a new cycle: every value on that cycle gets the cycle length, and the values before the cycle get larger lengths according to their distance from it. The candidates are generated by following the chain itself, and the filtering is exactly the first repeated value, which tells us where the non-repeating part ends.

Pseudocode

Precompute the factorials of the digits 0 through 9.
Create an empty cache of chain lengths.
Set the answer count to 0.

For each starting value below one million:
    Follow the digit-factorial map, recording values in order and remembering the first position of each value

    If the walk reaches a value already stored in the cache:
        work backward through the recorded path and assign lengths using the known tail length

    Otherwise a value repeats inside the current path:
        locate the first occurrence of that repeated value
        assign the cycle length to every value on the cycle
        then work backward through the prefix, increasing the length by one at each step

    If the starting value has chain length 60:
        increase the answer count

Return the answer count.

Complexity Analysis

Time: Each value in $[1, M]$ (where $M = 2{,}540{,}160$) is processed at most once due to memoization. Computing $f$ costs $O(\log n)$ per evaluation. The main loop iterates $N = 10^6$ times. Total:

where $D = O(\log N)$ is the cost per digit-factorial computation. Since $M = O(N)$, this simplifies to $O(N \log N)$.

• Time: $O(N \log N)$.
• Space: $O(N + M) = O(N)$ for the memoization cache.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Precompute digit factorials
    int fact[10];
    fact[0] = 1;
    for (int i = 1; i <= 9; i++) fact[i] = fact[i-1] * i;

    auto digit_fact_sum = [&](int n) -> int {
        if (n == 0) return 1;
        int s = 0;
        while (n > 0) {
            s += fact[n % 10];
            n /= 10;
        }
        return s;
    };

    const int LIMIT = 1000000;
    const int CACHE_SIZE = 3000001;  // f(n) <= 2,540,160 for n < 10^7
    vector<int> chain_len(CACHE_SIZE, 0);

    int count = 0;
    for (int start = 1; start < LIMIT; start++) {
        vector<int> chain;
        unordered_map<int, int> position;
        int cur = start;
        while (position.find(cur) == position.end() && !(cur < CACHE_SIZE && chain_len[cur] > 0)) {
            position[cur] = (int)chain.size();
            chain.push_back(cur);
            cur = digit_fact_sum(cur);
        }

        if (cur < CACHE_SIZE && chain_len[cur] > 0) {
            int length = chain_len[cur];
            for (int i = (int)chain.size() - 1; i >= 0; i--) {
                length += 1;
                int val = chain[i];
                if (val < CACHE_SIZE)
                    chain_len[val] = length;
            }
        } else {
            int cycle_start = position[cur];
            int cycle_length = (int)chain.size() - cycle_start;

            for (int i = cycle_start; i < (int)chain.size(); i++) {
                int val = chain[i];
                if (val < CACHE_SIZE)
                    chain_len[val] = cycle_length;
            }

            int length = cycle_length;
            for (int i = cycle_start - 1; i >= 0; i--) {
                length += 1;
                int val = chain[i];
                if (val < CACHE_SIZE)
                    chain_len[val] = length;
            }
        }

        if (chain_len[start] == 60) count++;
    }

    cout << count << endl;
    return 0;
}

"""
Project Euler Problem 74: Digit Factorial Chains

Count starting numbers below 1,000,000 whose digit factorial chain
contains exactly 60 non-repeating terms.

Uses memoized chain-length computation (Lemma: L(n) = 1 + L(f(n))
when n is not in a cycle).
"""

import math


def solve():
    fact = [math.factorial(d) for d in range(10)]

    def digit_fact_sum(n):
        if n == 0:
            return fact[0]
        s = 0
        while n > 0:
            s += fact[n % 10]
            n //= 10
        return s

    LIMIT = 1_000_000
    cache = {}

    def chain_length(n):
        if n in cache:
            return cache[n]

        chain = []
        position = {}
        cur = n
        while cur not in position and cur not in cache:
            position[cur] = len(chain)
            chain.append(cur)
            cur = digit_fact_sum(cur)

        if cur in cache:
            length = cache[cur]
            for val in reversed(chain):
                length += 1
                cache[val] = length
            return cache[n]

        cycle_start = position[cur]
        cycle_length = len(chain) - cycle_start

        for i in range(cycle_start, len(chain)):
            cache[chain[i]] = cycle_length

        length = cycle_length
        for i in range(cycle_start - 1, -1, -1):
            length += 1
            cache[chain[i]] = length

        return cache[n]

    count = 0
    for start in range(1, LIMIT):
        if chain_length(start) == 60:
            count += 1

    return count


if __name__ == "__main__":
    answer = solve()
    assert answer == 402
    print(answer)