# Project Euler

### A Taste of Number Theory

#### 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 = 14 + 64 + 34 + 44 8208 = 84 + 24 + 04 + 84 9474 = 94 + 44 + 74 + 44

As 1 = 14 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 95 * 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 95 * 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 95 * 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 95 * 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 95 * 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);
}
}
```