Problem 74: Digit Factorial Chains

Project Euler Problem 74 Solution

EulerSolve provides an optimized solution for Project Euler Problem 74, Digit Factorial Chains, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

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

Problem page: Project Euler 74
Factorial: Wikipedia - Factorial
Factorion: Wikipedia - Factorion
Memoization: Wikipedia - Memoization
Functional graph: Wikipedia - Functional graph
Cycle detection: Wikipedia - Cycle detection

Problem 74 source code

C++

#include <array>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

struct Options {
    int limit = 1000000;
    int target_length = 60;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        if (parse_int_after_prefix(arg, "--target-length=", options.target_length)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.limit >= 1 && options.target_length >= 1;
}

int next_value(int n, const std::array<int, 10>& fac) {
    int sum = 0;
    do {
        sum += fac[static_cast<std::size_t>(n % 10)];
        n /= 10;
    } while (n > 0);
    return sum;
}

int chain_length(int start,
                 const std::array<int, 10>& fac,
                 std::unordered_map<int, int>& memo) {
    std::vector<int> order;
    order.reserve(80U);
    std::unordered_map<int, int> seen;

    int n = start;
    while (true) {
        auto it_memo = memo.find(n);
        if (it_memo != memo.end()) {
            int len = it_memo->second;
            for (int i = static_cast<int>(order.size()) - 1; i >= 0; --i) {
                ++len;
                memo[order[static_cast<std::size_t>(i)]] = len;
            }
            return memo[start];
        }

        auto it_seen = seen.find(n);
        if (it_seen != seen.end()) {
            const int loop_start = it_seen->second;
            const int loop_len = static_cast<int>(order.size()) - loop_start;

            for (int i = loop_start; i < static_cast<int>(order.size()); ++i) {
                memo[order[static_cast<std::size_t>(i)]] = loop_len;
            }

            int len = loop_len;
            for (int i = loop_start - 1; i >= 0; --i) {
                ++len;
                memo[order[static_cast<std::size_t>(i)]] = len;
            }
            return memo[start];
        }

        seen[n] = static_cast<int>(order.size());
        order.push_back(n);
        n = next_value(n, fac);
    }
}

int solve(const int limit, const int target_length) {
    std::array<int, 10> fac{};
    fac[0] = 1;
    for (int d = 1; d <= 9; ++d) {
        fac[static_cast<std::size_t>(d)] = fac[static_cast<std::size_t>(d - 1)] * d;
    }

    std::unordered_map<int, int> memo;
    memo.reserve(2000000U);

    int count = 0;
    for (int n = 1; n < limit; ++n) {
        if (chain_length(n, fac, memo) == target_length) {
            ++count;
        }
    }

    return count;
}

bool run_checkpoints() {
    std::array<int, 10> fac{};
    fac[0] = 1;
    for (int d = 1; d <= 9; ++d) {
        fac[static_cast<std::size_t>(d)] = fac[static_cast<std::size_t>(d - 1)] * d;
    }

    std::unordered_map<int, int> memo;
    if (chain_length(69, fac, memo) != 5) {
        std::cerr << "Checkpoint failed for start=69" << '\n';
        return false;
    }
    if (chain_length(78, fac, memo) != 4) {
        std::cerr << "Checkpoint failed for start=78" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit, options.target_length) << '\n';
    return 0;
}

Python

import sys

def parse_int_after_prefix(arg, prefix):
    if not arg.startswith(prefix):
        return False, 0
    tail = arg[len(prefix):]
    if not tail:
        return False, 0
    
    try:
        value = int(tail)
        if str(value) != tail:  # Check for leading zeros or invalid characters
            return False, 0
        return True, value
    except ValueError:
        return False, 0

def parse_arguments(args):
    options = {
        'limit': 1000000,
        'target_length': 60,
        'run_checkpoints': True
    }
    
    i = 1
    while i < len(args):
        arg = args[i]
        if arg == "--skip-checkpoints":
            options['run_checkpoints'] = False
            i += 1
            continue
        
        found, value = parse_int_after_prefix(arg, "--limit=")
        if found:
            options['limit'] = value
            i += 1
            continue
        
        found, value = parse_int_after_prefix(arg, "--target-length=")
        if found:
            options['target_length'] = value
            i += 1
            continue
        
        print(f"Unknown argument: {arg}", file=sys.stderr)
        return None
    
    if options['limit'] < 1 or options['target_length'] < 1:
        return None
    
    return options

def next_value(n, fac):
    total = 0
    while n > 0:
        total += fac[n % 10]
        n //= 10
    return total

def chain_length(start, fac, memo):
    order = []
    seen = {}
    
    n = start
    while True:
        if n in memo:
            length = memo[n]
            for i in range(len(order) - 1, -1, -1):
                length += 1
                memo[order[i]] = length
            return memo[start]
        
        if n in seen:
            loop_start = seen[n]
            loop_len = len(order) - loop_start
            
            for i in range(loop_start, len(order)):
                memo[order[i]] = loop_len
            
            length = loop_len
            for i in range(loop_start - 1, -1, -1):
                length += 1
                memo[order[i]] = length
            
            return memo[start]
        
        seen[n] = len(order)
        order.append(n)
        n = next_value(n, fac)

def run_checkpoints():
    fac = [1] * 10
    for d in range(1, 10):
        fac[d] = fac[d-1] * d
    
    memo = {}
    
    if chain_length(69, fac, memo) != 5:
        print("Checkpoint failed for start=69", file=sys.stderr)
        return False
    
    if chain_length(78, fac, memo) != 4:
        print("Checkpoint failed for start=78", file=sys.stderr)
        return False
    
    return True

def solve(limit, target_length):
    fac = [1] * 10
    for d in range(1, 10):
        fac[d] = fac[d-1] * d
    
    memo = {}
    
    count = 0
    for n in range(1, limit):
        if chain_length(n, fac, memo) == target_length:
            count += 1
    
    return count

def main():
    args = sys.argv[1:]
    
    options = parse_arguments(args)
    if options is None:
        sys.exit(1)
    
    if options['run_checkpoints'] and not run_checkpoints():
        sys.exit(2)
    
    result = solve(options['limit'], options['target_length'])
    print(result)

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Euler74 {
    static int[] fac = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    static Map<Integer, Integer> memo = new HashMap<>();

    static int chainLength(int n) {
        if (memo.containsKey(n))
            return memo.get(n);
        List<Integer> visited = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        int current = n;
        while (!seen.contains(current)) {
            if (memo.containsKey(current)) {
                int len = memo.get(current) + visited.size();
                for (int i = 0; i < visited.size(); i++)
                    memo.put(visited.get(i), len - i);
                return memo.get(n);
            }
            seen.add(current);
            visited.add(current);
            int next = 0;
            for (char c : Integer.toString(current).toCharArray())
                next += fac[c - '0'];
            current = next;
        }
        int cycleStart = visited.indexOf(current);
        int cycleLen = visited.size() - cycleStart;
        for (int i = 0; i < cycleStart; i++)
            memo.put(visited.get(i), visited.size() - i);
        for (int i = cycleStart; i < visited.size(); i++)
            memo.put(visited.get(i), cycleLen);
        return memo.get(n);
    }

    public static void main(String[] args) {
        int count = 0;
        for (int n = 1; n < 1000000; n++)
            if (chainLength(n) == 60)
                count++;
        System.out.println(count);
    }
}