Digit Fifth Powers

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

\begin{align} 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} \end{align}

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.

Let’s make it easier

Computation-wise, the problem is pretty simple as we’re dealing with relatively small numbers. But what’s the maximum number we have to check? For example, can a 7-digit number be equal to the sum of its digit raised to the power of five?

Once we know the upper bound, we can check all the numbers. That’s a naive approach, though. Because if we manage to prove that no such number can have 7 digits, then instead of checking all the numbers, we could as well generate the sets of possible candidates, such as:

\begin{align} 1^{5} + 1^{5} + 1^{5} + 1^{5} + 1^{5} + 1^{5}\\ 2^{5} + 1^{5} + 1^{5} + 1^{5} + 1^{5} + 1^{5}\\ 2^{5} + 2^{5} + 1^{5} + 1^{5} + 1^{5} + 1^{5} \end{align}

The boundary

For a single digit, the maximum value is \(9^{5}\). So if we denote the number of digits as \(n\), then the boundary we’re looking for is \(n * 9^{5}\).

For a 6-digit number, we’d be looking for a number lower than \(354294\). That makes sense, right? After all, \(354294\) is a 6-digit number itself, so anything lower than that works.

For a 7-digit number, our formula is evaluated to:

\begin{align} n * 9^{5} = 7 * 59049 = 413343 \end{align}

So, the maximum value of the sum of the digits would be \(413343\). It’s a 6-digit number though. In other words, numbers from \(1000000\) to \(9999999\) return at maximum \(413343\), which means that it’s never the same number.

So, we’ve proved that such number can be at most \(354294\).

Solution

The solution is pretty simple, as we only need to check \(354294\) numbers which is a quite low value. The code gets the digits of a given number, calculates their power of 5, sums all of them and checks if we get the initial number. Then all the numbers that match this conditions are summed.

A truly neat, functional solution!

object Euler030 extends EulerApp {

  override def execute(): Int =
    Iterator
      .from(2)
      .takeWhile(_ < 354294)
      .filter(n => digitsToPower(n, 5) == n)
      .sum

  private def digitsToPower(n: BigInt, power: Int): BigInt =
    getDigits(n).map(BigInt(_).pow(power)).sum

  private def getDigits(n: BigInt): List[Int] =
    n.toString().map(_.asDigit).toList

}