## Posts Tagged ‘prob34’

### Problem 34 – Factorials of Digits

October 31, 2009

In problem 34 we are supposed to find the sum of all numbers that are the sum of the factorials of their digits.

My first thought was to just loop through all the possible numbers, compute sums of factorials of digits, and see what numbers worked. To do this, we have to know a stopping point. Well, 9! is 362880, so the largest digit factorial sum (DFS) that could be made with $n$ digits is $362880n$. An $n$ digit number is always at least as big as $10^{n-1}$, so if $362880n<10^{n-1}$, then no number with $n$ digits (or more) will be equal to its DFS. It turns out that 8 digits is too many. So we could stop looking once we got to $7\cdot 9!=2540160$. We could clearly lower this bound some more, but let’s go with it for now.

Suppose we’ve got a function “fact” that returns the factorial of whatever number you give it. Then we can compute DFS using the following function:

def dfs(n):
""" Compute the sum of the factorials of the digits of n """
return sum(map(fact, map(int, str(n))))


I think that’s fun. Convert n to a string, then change the string to a list of digits (as integers), apply “fact” to each, and then sum. I’m sure I’ve used similar lines in other problems here.

Now, given this, we could, in theory, solve this problem with one more line:

print sum([n for n in xrange(10,7*fact(9)) if dfs(n) == n])


This certainly has the advantage of being readable. But I think it could be improved a bit, as it’s fairly slow.

The problem with this code is that we can quickly ignore lots of numbers, without computing the digit sum for each. If a number starts with a bunch of 1s, the DFS will only be so big. On the flip side, there’s no point in considering any 5 digit numbers with a 9 in them. Another issue with the code above, I expect, is that the dfs calculation used is not particularly fast.

Here’s some more efficient code:

fact = [1,1,2,6,24,120,720,5040,40320,362880]
digs = range(0,10)

""" All solutions with k digits, starting with head

assumes:
"""
if len(head) == k: # we have a k digit number
else:
return 0
rem = k-len(head) # number of digits remaining to append
smallsum = sumhead + rem*1 # smallest digit sum possible
largeval = smallval + 10**rem - 1 # largest value that could be made
largesum = sumhead + rem*fact[9] # largest digit sum possible
if(largeval < smallsum or smallval > largesum):
return 0