Detailed mathematical approach

Problem Summary

Let \(F(n)\) be the sum of the factorials of the decimal digits of \(n\). Problem 34 asks for all positive integers satisfying \(F(n)=n\), and then for the sum of the non-trivial ones. The equalities \(1=1!\) and \(2=2!\) are excluded because the problem is interested in numbers that arise as a genuine sum of digit factorials rather than a one-term identity.

So the target objects are the non-trivial fixed points of the digit-factorial map in base 10. The implementations solve the problem in a mathematically complete way: prove a finite search range, precompute the ten factorial values, and test every candidate inside that proven range.

Mathematical Approach

The entire method comes from three simple but decisive observations: every decimal digit contributes at most \(9!\), the number of digits forces a lower bound on \(n\), and factorials of digits can be reused through a tiny lookup table.

The Digit-Factorial Map

If the decimal digits of \(n\) are \(d_1,d_2,\dots,d_k\), define

$F(n)=d_1!+d_2!+\cdots+d_k!.$

We are looking for numbers with \(F(n)=n\). That is a fixed-point equation, but it is a very concrete one: each digit contributes independently through its factorial. The contribution of a zero digit is especially important, because \(0!=1\), not \(0\). This matters in the example \(40585\).

The implementations therefore precompute the ten values \(0!,1!,\dots,9!\) once, using the recurrence

$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$

After that, evaluating \(F(n)\) is just a digit scan with table lookups.

Why the Search Space Is Finite

Suppose \(n\) has exactly \(k\) decimal digits. Then each digit contributes at most \(9!=362{,}880\), so

$F(n)\le k\cdot 9!.$

On the other hand, every \(k\)-digit number satisfies

$n\ge 10^{k-1}.$

Therefore a \(k\)-digit solution can exist only if

$10^{k-1}\le k\cdot 9!.$

The left side grows exponentially with \(k\), while the right side grows only linearly. So beyond some digit length the inequality fails permanently, which means there can be only finitely many decimal solutions.

The Exact Bound Used by the Implementations

The code does not hard-code the bound; it derives it by advancing through digit lengths until the smallest number with that many digits is larger than the largest possible digit-factorial sum for that same length.

For seven digits we still have

$7\cdot 9!=2{,}540{,}160,$

which is large enough to cover all possible seven-digit candidates. But for eight digits,

$8\cdot 9!=2{,}903{,}040<10^7,$

so no eight-digit number can ever equal the sum of the factorials of its digits. Hence every solution lies in the interval

$10\le n\le 7\cdot 9!=2{,}540{,}160.$

Once this inequality is proved, a complete scan of that interval is not a heuristic. It is a proof-producing exhaustive search.

Worked Examples and Final Identification

The two non-trivial decimal factorions are easy to verify directly:

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

$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$

The second example shows why handling \(0!=1\) correctly is essential. Because the search over the entire proven interval finds no further values, these are the only non-trivial solutions in base 10.

The required total is therefore

$145+40585=40{,}730.$

How the Code Works

Precompute the Table and Discover the Bound

The C++, Python, and Java implementations first build the ten-entry factorial table iteratively. They then walk upward through possible digit lengths, keeping track of the smallest number with the current length and the largest digit-factorial sum compatible with that length. The first length for which the lower bound overtakes the upper bound is impossible, so the previous length yields the final search limit.

Test One Candidate by Stripping Digits

To evaluate a candidate, the implementation repeatedly takes the last decimal digit, adds the precomputed factorial of that digit to a running total, and removes the digit from the remaining prefix. After each iteration, the running total equals the sum of the factorials of the digits already peeled off. When no digits remain, the running total is exactly \(F(n)\), and comparing it with the original number decides whether the candidate is a factorion.

Accumulate the Valid Numbers

The scan begins at \(10\), which automatically excludes the one-digit trivialities. Every candidate satisfying \(F(n)=n\) is added to the final sum. Before the full sweep, the implementations also validate the two known non-trivial examples \(145\) and \(40585\); these checkpoints make sure the digit-factorial evaluation is correct before the exhaustive pass starts.

Complexity Analysis

Let

$U=7\cdot 9!=2{,}540{,}160.$

Each candidate requires one decimal digit scan, and every scanned candidate has at most seven digits. So the running time is

$O(U\cdot 7)=O(U),$

with a very small constant factor in practice.

The extra space is constant: only the ten factorial values and a handful of counters are stored. That is \(O(10)\), equivalently \(O(1)\).

Footnotes and References

1. Problem page: Project Euler 34
2. Factorion: Wikipedia - Factorion
3. Factorial: Wikipedia - Factorial
4. Fixed point: Wikipedia - Fixed point
5. Sequence of decimal factorions: OEIS A014080