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

#### The Catch

How to find the upper bound, or the stop point for checking if numbers can be written as the sum of fifth powers of their digits.

#### The Light

The lowest 4-digit number is 1,000, maximum digit-5th power sum is 9^{5} * 4 = 236,196. That means out of all 4-digit numbers, there are some numbers that can be written as the sum of fifth power of their digits (1,000 < 236,196).

The lowest 5-digit number is 10,000, maximum digit-5th power sum is 9^{5} * 5 = 295,245. That means out of all 5-digit numbers, there are some numbers that can be written as the sum of fifth power of their digits (10,000 < 295,245).

The lowest 6-digit number is 100,000, maximum digit-5th power sum is 9^{5} * 6 = 354,294. That means out of all 5-digit numbers, there are some numbers that can be written as the sum of fifth power of their digits (100,000 < 354,294).

The lowest 7-digit is 1,000,000, but their maximum digit-5th power sum only goes up to 9^{5} * 7 = 413,343. This indicates all 7-digit numbers cannot be written as the sum of fifth power of their digits (1,000,000 > 413,343). Since all 7-digit numbers are not valid, any numbers with more digits are also invalid. Thus, the 6-digit number can be a reasonable boundary. Upper limit is 9^{5} * 6 = **354,294**.

#### The Code

public class Problem30 { public static void main(String[] args) { int sum = 0; for(int i = 10; i < 354294; i++) { String s = Integer.toString(i); int tmpSum = 0; for(int y = 0; y < s.length(); y++) { tmpSum += (Character.getNumericValue(s.charAt(y)) * Character.getNumericValue(s.charAt(y)) * Character.getNumericValue(s.charAt(y)) * Character.getNumericValue(s.charAt(y)) * Character.getNumericValue(s.charAt(y))); } if(tmpSum == i) sum += i; } System.out.println(sum); } }