# Project Euler Problem 30: Digit Fifth Powers¶

The source code for this problem can be found here.

## Problem Statement¶

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

$\begin{split}1634 = 1^4 + 6^4 + 3^4 + 4^4 \\ 8208 = 8^4 + 2^4 + 0^4 + 8^4 \\ 9474 = 9^4 + 4^4 + 7^4 + 4^4\end{split}$

As $$1 = 1^4$$ is not a sum it is not included.

The sum of these numbers is $$1634 + 8208 + 9474 = 19316$$.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

## Solution Discussion¶

First, we need to establish a constraint on the size of the numbers we’ll consider.

Consider the number $$9 \dots 9$$, by summing the fifth powers of the decimal digits within this number, we get $$n \times 9^5$$, where $$n$$ is the number of digits. We also need the same $$n$$-digit number to potentially equal $$n \times 9 ^ 5$$. To find the search limit, find an $$n$$ where this is not possible:

$\begin{split}n = 1 \Rightarrow & 1 \times 9^5 = 59049 \\ n = 2 \Rightarrow & 2 \times 9^5 = 118098 \\ n = 3 \Rightarrow & 3 \times 9^5 = 177147 \\ n = 4 \Rightarrow & 4 \times 9^5 = 236196 \\ n = 5 \Rightarrow & 5 \times 9^5 = 295245 \\ n = 6 \Rightarrow & 6 \times 9^5 = 354294 \\ n = 7 \Rightarrow & 7 \times 9^5 = 413343\end{split}$

Since no seven digit number can be mapped to anything greater than $$413343$$, we can use the upper bound $$n \le 10^6$$.

The problem states that $$1 = 1^4$$ is invalid as it is a trivial sum of one term. We will assume that $$1 = 1^5$$ is similarly invalid. Observe that for any other one digit decimal number $$d$$, its fifth power exceeds itself (i.e. $$d^5 \gt d \mbox{ } \forall d \in [2, 9]$$).

Therefore, we only need consider the range $$10^1 \le n \lt 10^6$$.

Finally, observe that the mapping in this problem is commutative. That is, the order of the digits does not matter. For example, consider the two numbers $$123,321$$ and apply the mapping:

$\begin{split}123 \rightarrow 1^5 + 2^5 + 3^5 = 1 + 32 + 243 = 276 \\ 321 \rightarrow 3^5 + 2^5 + 1^5 = 243 + 32 + 1 = 276\end{split}$

So, we need only consider all possible combinations of decimal digits (with replacement) for numbers of lengths $$2$$ through $$7$$.

## Solution Implementation¶

from itertools import combinations_with_replacement

from lib.digital import digits_of, num_digits

def solve():
""" Compute the answer to Project Euler's problem #30 """
power = 5
for n in range(2, 6+1):
for digits in combinations_with_replacement(range(10), n):
mapped_value = sum((digit ** power for digit in digits))
if tuple(sorted(digits_of(mapped_value))) == digits and num_digits(mapped_value) == n:

solutions.problem30.solve()