Problem Analysis
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
narcissistic numbers
(also "Armstrong numbers") for the chosen exponent. The single-digit case is excluded because
1 = 1^5 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.
The bound comes from a counting argument. For exponent n, the largest digit-power sum a
k-digit number can produce is k * 9^n (every digit a 9). But the smallest
k-digit number is 10^(k-1). Once k * 9^n has fewer digits than
k itself, no k-digit number can equal its own digit-power sum, and the search must
terminate. Taking the
base-10 logarithm
of n * 9^n and rounding up gives the maximum number of digits any candidate can have;
for n = 5 this works out to 6 digits. The second key observation is that the digit-power
sum depends only on the multiset 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
combinations with replacement.
The number of such multisets of length k from 10 digits is C(10+k-1, k) - a
few thousand for k = 6 rather than a million. The complexity is therefore
O(C(10+k-1, k) * k), which is trivially small.
Solution Approach
Combinations-with-replacement enumeration (Python and C)
Both files implement the same algorithm, so I describe it once and note language differences at the end.
Step 1 - compute the search width. I evaluate
k = ceil(log10(n * 9^n)) 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 0^n = 0
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.
Step 2 - enumerate multisets. I walk over every non-decreasing sequence of length
k drawn from {0, ..., 9}. In Python this is handed to me directly by
itertools.combinations_with_replacement(range(10), k).
In C, lacking such an iterator, I keep an integer array indices[0..k-1] 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
combination with replacement
is visited twice.
Step 3 - candidate sum and verification. For each multiset I sum the n-th
powers of its elements to get a candidate num. A multiset's sum is only a genuine
narcissistic number
if the digits of num itself reproduce that sum. So I verify num > 9 (to
drop the trivial single-digit cases) and that the digit-power sum of num equals
num. In Python I re-expand via str(num) and sum the powers of each
character; in C the helper digit_power_sum peels digits off with repeated
% 10 and / 10.
Language differences. The Python solve is a single
sum(...) over a generator expression, using the
walrus operator
to bind num inline. The C version uses explicit loops, a manually advanced combination
array, and an integer power helper instead of pow() 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.