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)

def solvedigs(k, head = [], headval = 0, sumhead = 0):
    """ All solutions with k digits, starting with head

      len(head) <= k
    if len(head) == k: # we have a k digit number
        if headval == sumhead:
            return headval
            return 0
    rem = k-len(head) # number of digits remaining to append
    smallval = headval*(10**rem) # smallest value that could be made
    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
    return sum([solvedigs(k, head + [d], 10*headval + d, sumhead + fact[d])
                for d in digs
                if len(head) or d>0]) # no 0 leading digits!

if __name__ == "__main__":
    print sum([solvedigs(k) for k in xrange(2,8)])

I know I cheated with the global variable fact, but it is quicker than computing factorials every time we want to know them. And with problems of this size, having global variables really shouldn’t be an issue.

In the code above I pass around the digits of the number I’m considering, the value that digit string represents, and the sum of the factorials of those digits. Never involving strings (more precisely, string to/from integer conversions) seems like a good idea for efficiency in this problem.