# Project Euler 30: Digit fifth powers

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.

## Solution

In analogy to Problem 34, we can find a brute-force algorithm quite easily. As before, we need to find a reasonable upper bound, which follows the same justification and given the bound, the rest is quite trivial. So we naively say we form a number \(n=d \cdot 9^5\) and bind it into our number-length interval.

\[\begin{array}{rl} & 10^{d-1} \leq d \cdot 9^5 < 10^d\\ \Leftrightarrow & (d-1)log(10) \leq \log(d) + 5\log(9) < d\log(10)\\ \Leftrightarrow & (d-1)\leq \log_{10}(d) + 5\log_{10}(9) < d\\ \Leftrightarrow & d-\log_{10}(d) \leq 5.77 < d-\log_{10}(d)+1\\ \Rightarrow & d-\log_{10}(5) \leq 5.77 < d-\log_{10}(5)+1\\ \Leftrightarrow & d \leq 6.47 < d+1 \end{array}\]

From this derivation follows that the maximum upper bound can have at most 6 digits, which results in a 6 digits number of all 9. Summing over these six 9s, raised to the 5th power gives \(6\cdot 9^5=354294\). This new upper bound saves almost \(\frac{2}{3}\) of the previous search space. For the lower bound, we can skip all one-digit numbers right away, since the exponent of 5 is quite dominant - also similar to the factorial problem.

The implementation doesn't look any surprising. We pre-calculate the powers again:

var POW = []; for (var i = 0; i < 10; i++) POW[i] = Math.pow(i, 5);

Create a function to sum over the powers of the digit:

function powSum(n) { var sum = 0; while (n > 0) { sum+= POW[n % 10]; n = n / 10 | 0; } return sum; }

And finally sum over all proper numbers:

function solution() { var sum = 0; for (var i = 10; i <= 354294; i++) { if (i === powSum(i)) { sum+= i; } } return sum; }

One last thing: For a general \(e\) you could come to the idea that \((e + 1)\cdot 9^e\) is a sufficient upper bound. It is, but it fails to be enough for \(e>33\) due to the fact that \(O(10^e) \supseteq O((e + 1)\cdot 9^e\)).