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);
  }
}