Problem Description

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.

Analysis

These type of numbers are referred to as factorions and it’s easy to learn that only 4 exist: 1, 2, 145 & 40585. The problem description wants us to ignore 1 & 2 so the answer to this problem should become obvious.

But, let’s write a program anyway to search for factorions. As usual, when writing a brute force search algorithm, we must first determine our bounds. The lower bound is 10 because single digit candidates are to be ignored. The upper bound we discover as follows (from Wikipedia):

If n is a natural number of d digits that is a factorion, then 10^{d − 1} ≤ n ≤ 9!d and this fails to hold for d ≥ 8. Thus n has 7 digits and the maximum sum of factorials of digits for a 7 digit number is 9!7 = 2,540,160, which is the upper bound.

Afterwards, we learned 50,000 worked just fine.

Solution

Runs < 1 second in Perl.

my @fact = (1, 1, 2, 6, 24, 120, 720, 5_040, 40_320, 362_880); # 0 - 9 factorials 
my $s = 0;
 
for my $n (10..50_000) {
  $x=0;
  $x+=$fact[$_] for split //,$n;
  $s+=$n if $n == $x;
}
print "Answer to PE34 = $s";

Runs < 1 second in Python.

fact = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)
s = 0
 
for n in range(10, 50000):
  x = sum( fact[int(d)] for d in str(n) )
  if n == x: s+=n
 
print "Answer to PE34 = ",s

Comment

This is a finite set of numbers and therefore a brute force solution is completely acceptable. As long as it runs under a minute no further optimization is necessary.

• We use underscores in numeric literals for readability
• See Problem 74
• Mathematica: Sum[Boole[n == Tr[IntegerDigits[n]!]] n, {n, 3, 1*^5}]