Project Euler

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⁴ + 6⁴ + 3⁴ + 4⁴ 8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴ 9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ 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⁵ * 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 = 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⁵ * 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⁵ * 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⁵ * 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);
  }
}