Project Euler 30 Solution: 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.

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$$).

« Back to problem overview