Project Euler

Digit fifth powers

Problem 30

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

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 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.

At first glance, using brute force seems to be the most direct way to solve this problem after trying to find some mathematics formula failed. However, even with brute force, an upper limit must be establish to avoid running indefinitely. Following is the relationship between the left and the right side:

$10^{n-1} a_n + 10^{n-2} a_{n-1} + \ldots + 10^2 a_3 + 10 a_2 + a_1 = a_n^5 + a_{n-1}^5 + \ldots + a_3^5 + a_2^5 + a_1^5$

Let’s list the value of fifth power for all digits:

$1^5 = 1$
$2^5 = 32$
$3^5 = 243$
$4^5 = 1024$
$5^5 = 3125$
$6^5 = 7776$
$7^5 = 16807$
$8^5 = 32768$
$9^5 = 59049$

Notice that if $n=1$, even the smallest allowable digit (2) will still create a 2-digits number, thus, no 1-digit number is a possible solution. For $n=2$, any number contains a digit 3 or above is not a solution. For $n=3$, similarly, any number contains a digit 4 or above is not a solution. For $n=4$,  any number contains a digit 7 or above is not a solution. For $n=5$, it is possible to use all digits because $5 \cdot 9^5 = 295245$. For $n=6$, it is also possible to use all digits because $6 \cdot 9^5 = 354294$. For $n=7$, the minimum value on the left side can only be 1000000 but $7 \cdot 9^5 = 413343$, which mean there is no possible solution because the largest possible right side value is less than the smallest left side value. Thus, the maximum can set to 354294.

Lastly, one way to speed up the calculation is to store the calculated fifth power of all digits (list above) into memory for fast access to avoid duplicate calculation. Another improvement maybe skips all no solution digits listed above.