Detailed mathematical approach

Problem Summary

We seek all integers \(n \ge 2\) whose decimal expansion \(n=\sum_{i=0}^{k-1} a_i 10^i\) also satisfies

$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$

So the task is to find the fixed points of the fifth-power digit map, excluding the trivial case \(1\). For \(p=5\), there are exactly six such numbers: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\), and \(194979\). Their sum is \(443839\).

The mathematical core is not a closed-form formula. The real work is proving that only finitely many candidates can exist and then turning the check for each candidate into a tiny digit-by-digit computation.

Mathematical Approach

The C++, Python, and Java implementations are written for a general exponent \(p \ge 2\) and then run with \(p=5\). The central object is the digit-power map

$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$

where \(a_0,a_1,\dots,a_{k-1}\) are the decimal digits of \(n\). Problem 30 asks for the fixed points of \(F_5\).

The Fixed-Point Equation

If \(n\) has digits \(a_{k-1}\dots a_1 a_0\), then \(n\) is a solution exactly when

$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$

This is already problem-specific enough to guide the algorithm: nothing about the positions of the digits matters except the digits themselves, and each digit contributes independently through its fifth power.

Why the Search Is Finite

Let \(n\) be a \(k\)-digit number. Then \(n \ge 10^{k-1}\). On the other hand, each digit is at most 9, so the largest possible fifth-power digit sum for a \(k\)-digit number is

$F_5(n)\le k\cdot 9^5.$

Therefore, if

$10^{k-1} \gt k\cdot 9^5,$

then no \(k\)-digit number can satisfy \(F_5(n)=n\). The left-hand side is the smallest possible \(k\)-digit number, while the right-hand side is the largest sum of fifth powers its digits could ever produce. Once the inequality turns true, every longer length is impossible as well.

The Concrete Bound for Fifth Powers

Now compute the critical quantities:

$9^5=59049.$

For six digits, the largest possible sum is

$6\cdot 59049=354294,$

and six-digit numbers begin at \(100000\), so six-digit solutions are still possible. For seven digits, however,

$7\cdot 59049=413343 \lt 10^6=1000000.$

That proves there are no seven-digit solutions. Hence every valid number lies in the finite interval

$2 \le n \le 6\cdot 9^5 = 354294.$

The lower bound starts at 2 because the problem convention excludes 1.

Digit Stripping as the Core Identity

Write any positive integer as \(n=10q+r\) with \(0\le r\le 9\). Then the digit-power map satisfies

$F_p(n)=F_p(q)+r^p.$

This identity is exactly what the implementations use. Repeatedly taking the last digit \(r\), adding \(r^p\), and replacing \(n\) by \(q=\lfloor n/10\rfloor\) strips the decimal expansion from right to left. After each iteration, the running total already equals the contribution of the digits removed so far, while the remaining quotient still holds all unprocessed digits. That loop invariant makes the correctness of the computation immediate.

Because there are only ten possible digits, the values \(0^5,1^5,\dots,9^5\) are precomputed once. For the fifth-power case, the table is

$[0,1,32,243,1024,3125,7776,16807,24576,59049].$

Worked Example

Take \(n=194979\). Its digits are \(1,9,4,9,7,9\), so

$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$

Substituting the actual values gives

$1+59049+1024+59049+16807+59049=194979.$

So \(194979\) is indeed a fixed point of \(F_5\). The same direct computation confirms the other five solutions.

How the Code Works

Precompute the digit powers

The implementation first builds a ten-entry lookup table containing \(d^p\) for \(d=0,1,\dots,9\). This is the only place where exponentiation is performed; the main scan uses only table lookups, addition, modulo 10, and integer division.

Recover the upper bound programmatically

Instead of hard-coding the fact that the fifth-power case stops at six digits, the implementation searches for the first digit length \(k\) with

$10^{k-1} \gt k\cdot 9^p.$

Once that impossible length appears, the search ceiling is \((k-1)\cdot 9^p\). For \(p=5\), this produces the bound \(354294\) automatically.

Scan candidates and accumulate matches

Every integer from 2 up to the derived upper bound is tested. For each one, the implementation strips digits from right to left, accumulates the corresponding precomputed powers, and compares the resulting sum with the original integer. Whenever the two values match, that integer is added to the final total.

Check the logic on the fourth-power case

Before printing the default fifth-power answer, the implementations also verify the same machinery on the fourth-power variant. The known total there is \(19316\), so matching that value provides a compact built-in checkpoint.

Complexity Analysis

If \(U\) is the derived upper bound, then the running time is \(O(U\log_{10} U)\), because each candidate is processed once and each inner-loop iteration removes one decimal digit. The extra space usage is \(O(1)\): the lookup table has only ten entries, and the remaining storage is a handful of integers.

For Problem 30 specifically, \(U=354294\) and every candidate has at most 6 digits, so the total work is on the order of \(354294\times 6 \approx 2.1\times 10^6\) digit steps. That is why a direct exhaustive scan is not merely acceptable here; it is the natural consequence of the bound.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=30
2. Digit power sums and Armstrong numbers: Wikipedia - Narcissistic number
3. Additional background: MathWorld - Narcissistic Number
4. Decimal positional notation: Wikipedia - Positional notation
5. Exponentiation: Wikipedia - Exponentiation