When I get into a slump (at work, while grading, etc.), one of my new-found activities to get myself rolling again is to find a Project Euler problem that I can solve before the cookie on the site expires. This one took about two minutes to form an algorithm for, another minute or so to code, and then 40 seconds to execute. I normally try to optimize these programs, but in this case I was just looking for a solution as fast as I could generate one.
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.
Path to a Solution
Let’s assume that an integer $d$ has $n$ digits and that $d$ is the sum of the factorials of those $n$ digits. How big can $n$ be? We quickly find that $n<8$ since the largest sum of factorials we can produce from an 8-digit number is itself a 7-digit number (set all digits equal to 9 and look at $8\times 9!$, which only has 7 digits). So, we know the numbers that we're looking at are at most 7-digit numbers. Since $9999999$ would give $7\times 9!=2,540,160$, we have the following implementation in Sage:
import time start = time.time() # cache the factorials F = [factorial(ZZ(i)) for i in range(0,10,1)] S = 0 for i in range(3,2540161,1): # form sums of factorials D = sum([F[j] for j in ZZ(i).digits()]) # is the sum of factorials equal to original number? if D == i: S += D elapsed = time.time() - start print "Result %s found in %s seconds." % (S, elapsed)
When executed, we get the correct result.
Result 40730 found in 41.8051738739 seconds.
In fact, there are only two numbers that have this property: 145 and 40585. In the end, the only thing I actually got from using Sage is the factorial function (and I also have to force the iterator values to be Sage integers).