notes.html
problem 30 · 74 lines
<article>
<h3>Problem Analysis</h3>
<p>
I want every integer with more than one digit that equals the sum of the fifth powers of its own
digits. Numbers with this self-referential property are called
<a class="reference-source" href="https://en.wikipedia.org/wiki/Narcissistic_number" rel="noopener noreferrer" target="_blank">narcissistic numbers</a>
(also "Armstrong numbers") for the chosen exponent. The single-digit case is excluded because
<code>1 = 1^5</code> is a value, not a sum. At first glance the search looks unbounded - there are
infinitely many integers - so the first and most important job is to derive a finite ceiling beyond
which no solution can exist.
</p>
<p>
The bound comes from a counting argument. For exponent <em>n</em>, the largest digit-power sum a
<em>k</em>-digit number can produce is <code>k * 9^n</code> (every digit a 9). But the smallest
<em>k</em>-digit number is <code>10^(k-1)</code>. Once <code>k * 9^n</code> has fewer digits than
<em>k</em> itself, no <em>k</em>-digit number can equal its own digit-power sum, and the search must
terminate. Taking the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Common_logarithm" rel="noopener noreferrer" target="_blank">base-10 logarithm</a>
of <code>n * 9^n</code> and rounding up gives the maximum number of digits any candidate can have;
for <em>n = 5</em> this works out to 6 digits. The second key observation is that the digit-power
sum depends only on the <em>multiset</em> of digits, not their order, because addition is
commutative. So rather than scanning up to a million integers, I enumerate only sorted digit
combinations using
<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>.
The number of such multisets of length <em>k</em> from 10 digits is <code>C(10+k-1, k)</code> - a
few thousand for <em>k = 6</em> rather than a million. The complexity is therefore
<code>O(C(10+k-1, k) * k)</code>, which is trivially small.
</p>
<h3>Solution Approach</h3>
<h4>Combinations-with-replacement enumeration (Python and C)</h4>
<p>
Both files implement the same algorithm, so I describe it once and note language differences at the
end.
</p>
<p>
<strong>Step 1 - compute the search width.</strong> I evaluate
<code>k = ceil(log10(n * 9^n))</code> to fix the number of digits I will enumerate. I use exactly
this length and no fewer because any narcissistic number with fewer digits is still discovered: its
missing leading positions simply appear in the multiset as zeros, and <code>0^n = 0</code>
contributes nothing to the sum. Enumerating a single fixed length keeps the loop structure clean - I
do not need a separate pass per digit count.
</p>
<p>
<strong>Step 2 - enumerate multisets.</strong> I walk over every non-decreasing sequence of length
<em>k</em> drawn from <code>{0, ..., 9}</code>. In Python this is handed to me directly by
<a class="reference-source" href="https://docs.python.org/3/library/itertools.html#itertools.combinations_with_replacement" rel="noopener noreferrer" target="_blank"><code>itertools.combinations_with_replacement</code></a>(<code>range(10), k</code>).
In C, lacking such an iterator, I keep an integer array <code>indices[0..k-1]</code> and advance it
lexicographically: find the rightmost position that is not yet 9, increment it, and flood-fill every
position to its right with that same value. The flood-fill preserves the non-decreasing invariant
and keeps each multiset in exactly one canonical form, so no
<a class="reference-source" href="https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition" rel="noopener noreferrer" target="_blank">combination with replacement</a>
is visited twice.
</p>
<p>
<strong>Step 3 - candidate sum and verification.</strong> For each multiset I sum the <em>n</em>-th
powers of its elements to get a candidate <code>num</code>. A multiset's sum is only a genuine
<a class="reference-source" href="https://en.wikipedia.org/wiki/Narcissistic_number" rel="noopener noreferrer" target="_blank">narcissistic number</a>
if the digits of <code>num</code> itself reproduce that sum. So I verify <code>num > 9</code> (to
drop the trivial single-digit cases) and that the digit-power sum of <code>num</code> equals
<code>num</code>. In Python I re-expand via <code>str(num)</code> and sum the powers of each
character; in C the helper <code>digit_power_sum</code> peels digits off with repeated
<code>% 10</code> and <code>/ 10</code>.
</p>
<p>
<strong>Language differences.</strong> The Python <code>solve</code> is a single
<code>sum(...)</code> over a generator expression, using the
<a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#assignment-expressions" rel="noopener noreferrer" target="_blank">walrus operator</a>
to bind <code>num</code> inline. The C version uses explicit loops, a manually advanced combination
array, and an integer power helper instead of <code>pow()</code> in the hot path. The algorithm is
identical; the C build is roughly 50x faster on the main case purely because of compiled native code
versus interpreter overhead.
</p>
</article>