Project Euler

A Taste of Number Theory

Problem 34: Digit Factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: as 1! = 1 and 2! = 2 are not sums they are not included.

The Catch

How to determine the upper bound of the search range.
How to efficiently calculate factorial.
How to efficiently manipulate the digits to find their sum.

The Light

Similar to the analysis in Problem 30:
The lowest 7-digit number is 1,000,000, the maximum sum of factorial of their digits is 9! * 7 = 2,540,160.
The lowest 8-digit number is 10,000,000, the maximum sum of factorial of their digits is only 9! * 8 = 2,903,040. This indicates no 8-digit number can be written as the sum of factorial of their digit. Upper bound is 2,540,160.


In this problem, only 0! to 9! are needed, so calculate their results and store in an array to avoid repeated calculations.


Similar to the technique in Problem 37, perform a modulus of 10 on a number to get its last digit. Take advantage of this to calculate the digit sum.

The Code

public class Problem34
{
  public static void main(String[] args)
  {
    int sum = 0;
    int[] fact = fact();
	
    for(int i = 10; i <= 2540160; i++)
    {
      int tmp = i;	  
      int tmpSum = 0;
      while(tmp > 0)
      {
        tmpSum += fact[tmp % 10];
    	tmp /= 10;
      }
	  
      if(tmpSum == i)
        sum += i;
    }
    System.out.println(sum);
  }
  
  public static int[] fact()
  {
    int[] fact = new int[10];
    fact[0] = 1;
    for(int i = 1; i < fact.length; i++)
    {
      int tmp = i;
      int result = 1;
      while(tmp > 1)
      {
        result *= (tmp--);
      }
      fact[i] = result;
    }
    return fact;
  }
}