Problem 30: Digit Fifth Powers

Mathematical Development

Definition 1. For a positive integer $n$ with decimal digits $d_1, d_2, \ldots, d_m$, define the digit power sum of order $k$ as $\sigma_k(n) = \sum_{i=1}^{m} d_i^k$. A number $n \geq 2$ is a narcissistic number of order $k$ (also called a pluperfect digital invariant) if $\sigma_k(n) = n$.

Theorem 1 (Finiteness of Search Space). For any fixed $k \geq 2$, the set $\{n \geq 2 : \sigma_k(n) = n\}$ is finite. In particular, every such $n$ satisfies $n \leq U_k$, where $U_k$ is computable.

Proof. A $d$-digit number satisfies $n \geq 10^{d-1}$. The maximum value of $\sigma_k(n)$ for a $d$-digit number is $d \cdot 9^k$, since each digit is at most 9. For $\sigma_k(n) = n$ to hold, we need $d \cdot 9^k \geq 10^{d-1}$. Since $10^{d-1}$ grows exponentially in $d$ while $d \cdot 9^k$ grows linearly, there exists a threshold $D_k$ beyond which $d \cdot 9^k < 10^{d-1}$, making the equation $\sigma_k(n) = n$ impossible. Therefore $n$ has at most $D_k$ digits, and $n \leq D_k \cdot 9^k$. $\square$

Lemma 1 (Upper Bound for $k = 5$). If $\sigma_5(n) = n$, then $n \leq 354294$.

Proof. We have $9^5 = 59049$. For a $d$-digit number, $\sigma_5(n) \leq d \cdot 59049$. We need $d \cdot 59049 \geq 10^{d-1}$:

For $d \geq 7$, $d \cdot 59049 < 10^{d-1}$, so no $d$-digit number with $d \geq 7$ can be narcissistic of order 5. Hence $n$ has at most 6 digits and $n \leq 6 \cdot 9^5 = 354294$. $\square$

Theorem 2 (Completeness of Exhaustive Search). The exhaustive search over $\{2, 3, \ldots, 354294\}$ finds all narcissistic numbers of order 5.

Proof. By Lemma 1, every narcissistic number of order 5 lies in $[2, 354294]$. For each $n$ in this range, we compute $\sigma_5(n)$ directly and check whether $\sigma_5(n) = n$. Since the search range contains all candidates, the enumeration is complete. $\square$

Theorem 3 (Enumeration of Solutions). The narcissistic numbers of order $5$ (with $n \geq 2$) are exactly:

Proof. By exhaustive search over $[2, 354294]$, these are the only $n$ satisfying $\sigma_5(n) = n$. $\square$

Corollary (Answer). The sum of all narcissistic numbers of order 5 is

Editorial

We perform a bounded exhaustive search. The algorithm precomputes the fifth power of each digit, iterates through every candidate from 2 up to the proven upper bound $6 \cdot 9^5$, computes the sum of the fifth powers of its digits, and adds the number when the digit-power sum matches the original value. This is sufficient because Lemma 1 shows that no solution can lie above that bound.

Pseudocode

Algorithm: Sum of Numbers Equal to the Sum of Fifth Powers of Their Digits
Require: The decimal digit set {0, 1, ..., 9}.
Ensure: The sum of all integers that equal the sum of the fifth powers of their decimal digits.
1: Precompute w(d) ← d^5 for each digit d.
2: Initialize total ← 0.
3: For each candidate n in {2, 3, ..., 6 · 9^5}, compute s ← sum of w(d) over the decimal digits d of n.
4: If s = n, update total ← total + n.
5: Return total.

Complexity Analysis

Proposition (Time Complexity). The algorithm runs in $O(U \cdot \log_{10} U)$ time where $U = 354294$.

Proof. The outer loop iterates $U - 1$ times. For each $n$, extracting digits and summing their fifth powers takes $\lfloor \log_{10} n \rfloor + 1 \leq 6$ iterations. The fifth-power lookup is $O(1)$ via the precomputed table. Total: $O(U \cdot 6) = O(U)$. More precisely, $U \cdot \lceil \log_{10} U \rceil \approx 354294 \times 6 \approx 2.1 \times 10^6$ operations. $\square$

Proposition (Space Complexity). The algorithm uses $O(1)$ auxiliary space (the precomputed table has fixed size 10).

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    int pow5[10];
    for (int i = 0; i < 10; i++)
        pow5[i] = i * i * i * i * i;

    int total = 0;
    for (int n = 2; n <= 354294; n++) {
        int s = 0, t = n;
        while (t > 0) {
            s += pow5[t % 10];
            t /= 10;
        }
        if (s == n)
            total += n;
    }

    cout << total << endl;
    return 0;
}

def solve():
    pow5 = [i**5 for i in range(10)]
    total = 0
    for n in range(2, 6 * 9**5 + 1):
        s, t = 0, n
        while t:
            s += pow5[t % 10]
            t //= 10
        if s == n:
            total += n
    print(total)

if __name__ == "__main__":
    solve()