Problem 30: Digit Fifth Powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: $\begin{aligned} 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{aligned}$

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

Let $f (n)$ be the sum of the fifth powers of the digits of $n$ . The maximum value of $f$ for any $k$ -digit number is $9^{5} k = 59049 k$ , and the minimum value of any $k$ -digit number is $10^{k - 1}$ . Because $59049 k < 10^{k - 1}$ for $k \geq 7$ , $f (n) < n$ for $n \geq 10^{6}$ ; and because $f (n) \leq 9^{5} \times 6 = 354294$ for $n < 10^{6}$ , $f (n) < n$ for $n \geq 354295$ . This considerably cuts down on the values we have to check, even if we have to check those values by force.

Python Code

def p30():
	res = 0
	for n in range(2, 354294):
		ds, n_copy = 0, n
		while n_copy > 0:
			ds += (n_copy % 10) ** 5
			n_copy //= 10
		if ds == n:
			res += n
	return res

Previous Problem Next Problem

Back to Project Euler