notes.html

problem 34 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
I am asked to find every number that equals the sum of the <a class="reference-source" href="https://en.wikipedia.org/wiki/Factorial" rel="noopener noreferrer" target="_blank">factorials</a> of its own decimal digits, the canonical example being 145 = 1! + 4! + 5!. Any search problem of this shape begins with the same question: what bounds the search space? Without an upper limit the candidate set is infinite, so I need an analytic argument to make it finite. The argument is a counting one. The largest digit factorial is 9! = 362880, so a d-digit number can produce a digit factorial sum of at most d * 362880. For d = 8 that ceiling is 2,903,040 - a number with only seven digits. An eight-digit number can therefore never equal its own digit factorial sum, because the sum is too small to reach eight digits. This proves that I only need to examine numbers with at most seven digits, capping the brute-force search at roughly ten million candidates.
</p>
<p>
The second and more powerful observation is one of symmetry: the digit factorial sum depends only on the <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiset" rel="noopener noreferrer" target="_blank">multiset</a> of digits - the collection of digit values with their multiplicities but without regard to order - not on the sequence in which they appear. The numbers 145, 514, and 451 all share the identical digit factorial sum. So rather than scanning all ten million ordered numbers I only need to enumerate distinct digit multisets. Enumerating multisets is precisely the operation called <a class="reference-source" href="https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition" rel="noopener noreferrer" target="_blank">combinations with replacement</a>: choosing k digits from {0,...,9} where repetition is allowed but order is ignored. For length k there are C(k + 9, k) such multisets; summed over k = 2 through 7 the total is under 20000 candidates - roughly 500x fewer than the naive scan. The complexity is therefore O(sum over k of C(k+9, k)) candidate evaluations, each costing O(k) work to compute and verify - polynomial in the digit count and trivially fast in practice.
</p>
<h3>Solution Approach</h3>
<h4>Combinations-with-Replacement Filter (Python and C)</h4>
<p>
Both files implement the same algorithm: generate each digit multiset once, compute its factorial sum, then verify whether that sum is itself a number whose digits reproduce the multiset.
</p>
<p>
<strong>Step 1 - precompute the factorials.</strong> The ten digit factorials 0! through 9! are stored in a lookup table: a dictionary keyed by character in Python, a plain <code>int[10]</code> indexed by digit value in C. Both give O(1) factorial access and avoid recomputing factorials inside the inner loop.
</p>
<p>
<strong>Step 2 - enumerate multisets.</strong> For each length k from 2 to 7, I generate every non-decreasing sequence of length k over {0,...,9}. A non-decreasing sequence is the canonical representative of a multiset, so each multiset is visited exactly once with no deduplication pass needed. Python calls <code>itertools.combinations_with_replacement</code> directly. The C code drives the enumeration by hand: it starts with all positions at 0, then to advance it finds the rightmost position that is not yet 9, increments it, and sets every later position to that same value. This walks through all non-decreasing sequences in order.
</p>
<p>
<strong>Step 3 - compute the factorial sum</strong> of the digits in the combination.
</p>
<p>
<strong>Step 4 - apply three guards, cheapest first.</strong> Guard A: the factorial sum must have exactly k digits, otherwise it cannot be a k-digit candidate. Guard B: every digit in the combination must appear in the decimal representation of the factorial sum - a necessary (though not by itself sufficient) condition for the two digit multisets to coincide. Guard C: the definitive test - recompute the digit factorial sum of the sum itself and confirm it equals the sum. Guard C is what actually proves the curiosity property; the earlier guards exist only to discard the overwhelming majority of candidates cheaply before reaching it.
</p>
<p>
The differences are purely in representation. Python converts the sum to a string and tests digit membership with the <code>in</code> operator. C uses <code>snprintf</code> to render the sum, then counts digit frequencies in two <code>int[10]</code> arrays (<code>need</code> from the combination, <code>have</code> from the string) and verifies <code>need[d] &lt;= have[d]</code> for every digit - a stricter multiplicity check than Python's plain membership test, though both reach the same answer because guard C is exact regardless. C's definitive recomputation in <code>digit_factorial_sum</code> uses arithmetic (modulo 10, divide by 10) rather than string conversion.
</p>
</article>