Project Euler 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits
Project Euler 34 Problem Description
Project Euler 34: 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 asks 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: Factorion):
If n is a natural number of d digits that is a factorion, then 10d − 1 ≤ n ≤ 9!d. This fails to hold for d ≥ 8 thus n has at most 7 digits, and the first upper bound is 9,999,999. But the maximum sum of factorials of digits for a 7 digit number is 9!*7 = 2,540,160 establishing the second upper bound.
All factorials of digits at least 5 have the factors 5 and 2 and thus end on 0. Let 1abcdef denote our 7 digit number. If all digits a-f are all at least 5, the sum of the factorials – which is supposed to be equal to 1abcdef – will end on 1 (coming from the 1! in the beginning).
This is a contradiction to the assumption that f is at least 5. Thus, at least one of the digits a-f can be at most 4, which establishes 1!+4!+5*9!=1814425 as fifth upper bound. Assuming n is a 7 digit number, the second digit is at most 8. There are two cases: If a is at least 5, by the same argument as above one of the remaining digits b-f has to be at most 4. This implies an upper bound (since a is at most 8) of 1!+8!+4!+4*9!= 1491865, a contradiction to a being at least 5. Thus, a is at most 4 and the sixth upper bound is 1499999.
#Solution for Project Euler 34 from Euler import sof_digits s = sum(n for n in range(10, 1500000) if n == sof_digits(n)) print "Project Euler 34 Solution =", s
HackerRank version
HackerRank Project Euler 34 didn’t have much liberty in expanding this problem, so they created a version still requiring the sum of the factorial-digits. They provide a query, 10≤N≤105, and we report the total of all numbers less than N that divide the sum of the factorial of their digits.
Having a precalculated list of factorials of the numbers 1 through 9 saved having to calculate the factorials of the individual digits each time.
fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
Project Euler 34 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 34 Solution Python 2.7 source.
Afterthoughts
- 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.
- Function
sof_digitsis listed in Common Functions and Routines for Project Euler - Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A014080: Factorians: equal to the sum of the factorials of their digits in base 10.
- See also, :
- Mathematica solution:
Sum[Boole[n == Tr[IntegerDigits[n]!]] n, {n, 3, 1*^5}]
Discussion
No comments yet.