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 the fifth powers of their digits.

The problem asks for a brute-force solution, but we have a halting problem. How far do we need to go before we can be sure there are no sums of fifth power digits? Do we need to search until infinity, which means we can never solve the problem? We can limit the solution space because the solution will have lower and upper limits. An upper bound is a number with \(log 9^5\) digits.

In base ten, the highest digit is 9 and \(9^5=59049\), which has five digits. This implies that the highest possible number, which equals the sum of the fifth power of its digits is 5 times \(9^5=295245\). The lowest possible number is 2 times \(2^5 = 64\). All numbers with this property thus must range between these two values.

The code to solve this project first declares the exponent and determines the lower and upper boundaries of the solution space. Change the variable n to try other exponents. The loop cycles through the digits of each number and tests whether the sum of the fifth powers equals the number.

The digit sum of a number \(x\) in base 10 is given by:

$$\sum_{n=0}^{\lfloor \log_{10} x\rfloor} \frac{1}{10^n}(x \bmod 10^{n + 1} - x \bmod 10^n)$$

ProjectEuler

  ## Project Euler 30: Digit Fifth Powers
  m <- 5
  highest <- round(log10(9^m)) * 9^m
  answer <- 0
  for (x in 2:highest) {
      n <- 0:log10(x)
      power.sum <- sum(((1/10^n) * (x %% 10^(n + 1) - x %% 10^n))^m)
      if (power.sum == x) {
          print(x)
          answer <- answer + x
      }
  }
  print(answer)

The mathematics in this problem is about the digit sum, which is the sum of all digits in the relevant number base.

Computer scientists use digit sums in cryptography and data validation. You can find the digital sum base-10 numbers in sequence A007953 of the Online Encyclopedia of Integer Sequences. Checksum algorithms use digit sums as a quality assurance method. For example, the final digit in the ten-digit International Standard Book Numbers is a check digit. You can compute the check digit by multiplying each digit by its position in the ISBN number (alternating by 3 and 1), and taking the sum of these products. The check digit is 0 when the modules 10 of this modulus is zero, otherwise it is 10 minus the remainder. In R code, determining the check digit for a 13-digit ISBN number works as follows:

  ## Check ISB number
  check_isbn13 <- function(isbn) {
      isbn <- gsub(" |-", "", isbn)
      check_sum <- 0
      for (i in 1:12) {
          m <- ifelse(i %% 2 == 0, 3, 1)
          check_sum <- check_sum + m * as.numeric(substr(isbn, i, i))
      }
      check_sum <- ifelse(check_sum %% 10 == 0, 0, 10 - check_sum %% 10)
      check_sum == substr(isbn, 13, 13)
  }
  check_isbn13("978-0-9875669-4-2")