Project Euler Solution 30: Digit fifth powers

Problem 30: Digit fifth powers is a nice one because there are two parts to it.

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

• $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$

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.

We cannot possibly try out every number, there must be some upper bound. The largest that we can can have as a summand is $9^5 = 59,049$. We can have this as many times as there are digits. We can now try out how many digits we can have before the number exceeds the sum of 59,049:

• $1 \cdot 59,049 = 59,049 > 9$
• $2 \cdot 59,049 = 118,098 > 99$
• $3 \cdot 59,049 = 177,147 > 999$
• $4 \cdot 59,049 = 236,196 > 9,999$
• $5 \cdot 59,049 = 295,245 > 99,999$
• $6 \cdot 59,049 = 354,294 < 999,999$

From this we learn that at most six digit numbers are of interest here. We can also have a bit of code which does that check for us:

def find_limit() -> int:
    for num_digits in itertools.count(1):
        number = num_digits * 9**5
        if len(str(number)) <= num_digits:
            return number

And then we just have to go through all these numbers and check them.

def solution() -> int:
    accumulator = 0
    for number in range(2, find_limit()):
        digit_sum = sum(int(digit) ** 5 for digit in str(number))
        if number == digit_sum:
            accumulator += number
    return accumulator

That's it, it takes 495 ms to run. This problem needed a bit of an insight to get the upper limit. Everything else is just programming.