Project Euler Solution #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⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ 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\)).