Detailed mathematical approach

Problem Summary

For a positive integer \(n\), define

$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$

and then define

$sf(n)=s\bigl(f(n)\bigr),$

where \(s(x)\) is the ordinary decimal digit sum.

For each \(i\ge 1\), the problem introduces

$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$

The goal is to compute

$\sum_{i=1}^{150} sg(i).$

A direct search over \(n\) is completely impractical. The code therefore changes viewpoint: it searches over the value

$y=f(n),$

derives the smallest decimal \(n\) compatible with that \(y\), and uses a bitset dynamic program to find all relevant \(y\) grouped by decimal digit sum and residue modulo \(9!\).

Mathematical Approach

1. Search Over \(y=f(n)\) Instead of Over \(n\)

If the digit \(d\) appears \(c_d\) times in \(n\), then

$f(n)=\sum_{d=0}^{9} c_d\,d!.$

So a number \(n\) is completely described, for the purposes of \(f\), by the multiplicities of its digits. Once a target value \(y\) is fixed, the question becomes:

Among all digit multisets whose factorial sum is \(y\), which multiset yields the smallest decimal integer?

For any fixed multiset of digits, the smallest corresponding integer is obtained by arranging the digits in nondecreasing order. So for each \(y\), we only need the lexicographically smallest valid multiset.

2. Why a Minimal Candidate Never Needs the Digit 0

This is one of the key structural facts behind the code.

First, note that

$0!=1!=1.$

If a candidate multiset contains both a 0 and a 1, then we may replace that pair by a single digit 2, because

$0!+1!=1+1=2=2!.$

This preserves \(f(n)\) while shortening the decimal length, so the original number cannot have been minimal.

If a candidate contains a 0 but no 1, then its smallest nonzero digit is at least 2. Replacing one 0 by a 1 keeps \(f(n)\) unchanged, and after sorting the digits the resulting positive integer is smaller, because a leading 1 is better than a leading digit \(\ge 2\) followed by an internal 0.

Therefore, in a truly minimal \(g(i)\), zeros never appear. That is why the implementation only stores counts for digits \(1,\dots,9\).

3. The Carry Rule and Canonical Factorial Representation

The next crucial identity is

$(d+1)!=(d+1)\,d!.$

So whenever a digit multiset contains at least \(d+1\) copies of the digit \(d\), we may replace those \(d+1\) copies by a single digit \(d+1\). This keeps the factorial sum unchanged and strictly shortens the decimal length.

Consequently, in any minimal solution we must have

$0\le c_d\le d\qquad(1\le d\le 8).$

Repeatedly applying these carries produces a unique normalized expansion

$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$

where

$0\le c_d\le d\qquad(1\le d\le 8),$

and \(c_9\) is unrestricted.

This is exactly the factorial number system, truncated at \(9!\). The tuple \((c_1,\dots,c_9)\) is the canonical multiset of digits attached to \(y\).

4. Why This Canonical Representation Gives the Smallest \(n\)

There are three reasons:

1. Sorting a fixed multiset in nondecreasing order gives the smallest decimal number for that multiset.

2. Any zero can be eliminated, so minimal candidates use only digits \(1,\dots,9\).

3. Any violation of \(c_d\le d\) can be repaired by a carry, which strictly shortens the decimal number.

Therefore the normalized factorial digits are not just a convenient encoding of \(y\): they are precisely the digit counts of the smallest decimal \(n\) with \(f(n)=y\).

If the normalized counts are \(c_1,\dots,c_9\), then the corresponding minimal decimal number is

$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9}.$

Its decimal digit sum is

$sg=\sum_{d=1}^{9} d\,c_d,$

and its length is \(c_1+\cdots+c_9\).

5. Worked Example: \(g(5)=25\)

The C++ code checks that

$g(5)=25.$

Indeed,

$f(25)=2!+5!=2+120=122,$

so

$sf(25)=s(122)=1+2+2=5.$

The canonical factorial representation of \(122\) is simply

$122=1\cdot 5!+1\cdot 2!,$

which corresponds to the multiset \(\{2,5\}\), hence to the decimal integer \(25\).

6. Another Example: \(g(20)=267\)

The second checkpoint is

$g(20)=267.$

This comes from

$f(267)=2!+6!+7!=2+720+5040=5762,$

and therefore

$sf(267)=s(5762)=5+7+6+2=20.$

This example is important because it shows the real target of the search: for fixed \(i\), we are not looking for numbers \(n\) whose own digit sum is \(i\); we are looking for numbers whose factorial-digit-sum value \(y=f(n)\) has decimal digit sum \(i\).

7. Why Residues Modulo \(9!\) Are Sufficient

Write

$y=q\cdot 9!+r,\qquad 0\le r<9!.$

Then \(q=c_9\), while the remainder \(r\) determines the lower coefficients \(c_1,\dots,c_8\) uniquely via the factorial system.

So inside one residue class modulo \(9!\), the only thing that changes is the number of 9s.

If we replace \(y\) by \(y+9!\), then the normalized digit multiset simply gains one extra digit 9. That makes the resulting decimal \(n\) longer, hence larger. Therefore, for each residue class, only the smallest compatible \(y\) can ever matter.

This is the reason the whole search is organized by the modulus

$9!=362880.$

8. Dynamic Programming on the Decimal Expansion of \(y\)

Because

$sf(n)=s\bigl(f(n)\bigr)=s(y),$

the condition \(sf(n)=i\) is equivalent to asking for a decimal integer \(y\) whose digit sum is \(i\).

The solver builds a DP state

$DP[\ell][s][r],$

meaning: there exists a decimal number of length \(\ell\), decimal digit sum \(s\), and residue \(r\bmod 9!\).

If a new digit \(d\) is placed in the next decimal position, the residue changes by

$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$

and the digit sum changes to \(s+d\). So the transition is

$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$

The implementation stores the whole residue layer for each pair \((\ell,s)\) as a bitset. Then “add digit \(d\)” becomes a cyclic rotation by

$d\cdot 10^{\ell}\bmod 9!$

followed by bitwise OR. That is exactly what rotate_or does.

9. Why Leading Zeros Do Not Break the Search

The DP starts at length \(0\) and allows transitions with digit \(0\), so formally it also represents numbers with leading zeros. This is harmless, because for each target digit sum \(i\) and each residue \(r\), the solver scans lengths in increasing order and picks the first reachable one.

Therefore the chosen \(\ell\) is the true shortest decimal length of \(y\), and within that length the backtracking step reconstructs the lexicographically smallest decimal representation.

10. Backtracking the Smallest \(y\)

For a fixed target \(i\) and residue \(r\), once the smallest reachable length \(\ell\) is known, the code reconstructs the smallest \(y\) greedily. At each position it tries digits

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

in that order, and checks whether the predecessor state remains feasible. The first successful digit is taken.

This produces the smallest decimal \(y\) among all numbers with the chosen length, digit sum, and residue.

11. Choosing the Best Candidate Across Residues

Each reconstructed \(y\) is decoded to its canonical factorial coefficients \(c_d\). That yields one candidate for \(g(i)\).

To compare two candidates, the code first compares their lengths. The shorter decimal number is always smaller. If lengths tie, then the lexicographically smaller sorted digit string wins, which is equivalent to saying that more copies of smaller digits are better. This is exactly what node_less implements.

Finally, once the best candidate for \(g(i)\) is known, the contribution to the global answer is

$sg(i)=\sum_{d=1}^{9} d\,c_d.$

12. Validation Checkpoints

The implementation includes three useful checks:

$g(5)=25,$

$g(20)=267,$

and

$\sum_{i=1}^{20} sg(i)=156.$

These validate the normalization logic, the residue search, and the final candidate ordering.

How the Code Works

The constructor precomputes \(10^\ell \bmod 9!\) for all \(\ell\le 18\), then calls build_dp() to fill the bitset table for every length up to 18 and every digit sum up to 150. For a target value \(i\), the routine best_node_for_sf(i) scans all residues modulo \(9!\), finds the smallest length where that residue is reachable, reconstructs the minimal decimal \(y\) with backtrace_min_number(), decodes it with node_from_y(), and keeps the smallest candidate according to node_less(). The outer function simply sums the digit sums \(sg(i)\).

The implementation chooses a maximum decimal length of 18 for \(y\); this is sufficient for the target range \(i\le 150\) used here and is supported by the built-in checkpoints.

Complexity Analysis

Let

$L=18,\qquad S=150,\qquad M=9!=362880.$

For each pair \((\ell,s)\), the DP stores a bitset over all \(M\) residues. So the memory usage is

$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$

machine words.

The main time cost is building this table and then scanning residues for each \(i\). Because residue transitions are done by bitset rotation and OR, the algorithm is massively word-parallel and far faster than any direct search over \(n\), or even over all decimal \(y\) with a given digit sum.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=254
2. Factorial number system: Wikipedia — Factorial number system
3. Digit sums: Wikipedia — Digit sum
4. Bit manipulation and bitsets: cp-algorithms — Bit manipulation
5. Mixed radix systems: Wikipedia — Mixed radix