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 """
    answer = 0
    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:
                answer += mapped_value
    return answer


expected_answer = 443839

solutions.problem30.solve()

Compute the answer to Project Euler’s problem #30