Archive for October, 2009

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

    assumes:
      len(head) <= k
    """
    if len(head) == k: # we have a k digit number
        if headval == sumhead:
            return headval
        else:
            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.

Advertisements

Problem 33 – Cancelling Fractions

October 30, 2009

49/98 = 4/8 if you cancel the 9s. This happens for few others fractions n/d where 0<n<d<100, and we’ll also ignore (n'\cdot 10)/(d'\cdot 10) for digits n',d'. Now take all these fractions that cancel like this, consider their product as a reduced fraction, and find the denominator. This is the challenge of problem 33.

Here’s what I came up with:

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def solve():
    fracs = [ ]
    conv = lambda t:int("%s%s" % t)
    for bothdig in xrange(1,10): # the digit that cancels
        for numdig in xrange(1,10): # digit left in numerator
            for dendig in xrange(1,10): # digit left in denom
            nums = map(conv, [(numdig,bothdig),(bothdig,numdig)]) # consider bother orderings
            dens = map(conv, [(dendig,bothdig),(bothdig,dendig)])
            for v in [(n,d) for n in nums for d in dens if n<d]:
                if v[0]*dendig == v[1]*numdig: # v[0]/v[1] = numdig/dendig
                    fracs += [ v ]
    p = reduce(lambda l,r:(l[0]*r[0],l[1]*r[1]),fracs) # multiply together solutions
    return p[1] / gcd(*p) # reduce the fraction, return denom

Certainly room for improvement, but it works.

Problem 32 – Pandigital Products

October 30, 2009

We say that n is a pandigital product if n=a\cdot b and the string “abn” obtained by concatenating the base-10 representations of a, b, and n contains all of the digits 1-9 exactly once (with no 0s). In problem 32 we are asked to find the sum of all pandigital products.

I ended up being not particularly fancy about this problem. Loop through enough values for n, and, for each n, loop through enough values for a, and see if you get a pandigital product with n, a, and n/a. We know that it is enough for a to venture up to \sqrt{n}, but what about bounds on n? If n has 5 digits, then to be a pandigital product, with factors a and b, the factors must be either 1 and 3 digits, or 2 and 2 digits. But 9*999 and 99*99 aren’t 5 digit numbers, so we know we can stop looking for n once we get to 10000. Similar reasoning shows that n must have more than 3 digits, and so, in fact, to be a pandigital product, n must have 4 digits (and since they must not be 0, and must be distinct, 1234 is the smallest possibility).

The following code seems to get the job done:

def ispandigprod(a,b,n):
    """ assumes a*b==n """
    # consider the digits in the string "abn"
    # remove 0s and duplicates (with filter, set)
    # if you've still got 9 elements, you're pandigital
    return len(set(filter(lambda t:t, map(int, "%s%s%s" % (a,b,n))))) == 9

def solve():
    """ return the sum of the pandigital products """
    ret = 0
    for n in xrange(1234,9876+1):
        a = 1
        included = False
        while(a < n**.5 + 1 and not included):
            if(n % a == 0):
                b = n//a
                if(ispandigprod(a,b,n)):
                    ret += n
                    included = True
            a += 1
    return ret

I’d honestly like a nicer solution for this problem. The loop I have is pretty stupid, and loops through far more choices than is worthwhile. In particular, I’d like to not think about any n or a that have a digit that is 0. To ignore n with a 0 digit, one could replace the “included = False” line (apparently line 10) with

  included = str(n).count("0") > 0

This seems to cut the run-time down by about 20% (or more), so is maybe worthwhile. I still expect this code could be improved by a bit, but I think I’ll stop here for now.

Current Problems

October 25, 2009

To date, there has been a widget in the right-hand column with the “current problems”. The original intention here was to have two per week. Of course, the original intention also involved some other authors.

I’m going to remove the “current problems” widget. I’ll still hope to do at least one problem per week.

Problem 31 – Coins

October 19, 2009

In problem 31, we are given a list of coin values and a target value, and asked how many ways we can make that target value with coins of the given denominations. I think this is probably a pretty standard programming exercise, and I’m embarassed it took me as long as it did. Anyway, here’s what I came up with, nothing too special:

import sys, time

def worker(target, coins):
    """ assume coins are sorted decreasing """
    if target == 0:
        return 1 # there's only one way to not have money?

    # get rid of coins bigger than the target
    while(len(coins) and target < coins[0]):
        coins = coins[1:]

    # some easy cases
    if not len(coins): # all coins are > target
        return 0
    if len(coins) == 1:
        return (target % coins[0] == 0) and 1 or 0

    # there are >=2 types of coins, all <= target
    return sum([worker(target - v, coins[1:])
                for v in xrange(0, target + 1, coins[0])])

def solve(target, coins):
    t = time.time()
    coins.sort()
    coins.reverse()
    ret = worker(target, coins)
    t = time.time() - t
    return [ret, t]

if __name__ == "__main__":
    print solve(int(sys.argv[1]), map(int,sys.argv[2:]))

I also had fun trying this another way. Instead of breaking down the target amount and doing things recursively, I thought about having a huge amount of coins around. The example problem had a target of 200, with denominations 1, 2, 5, 10, 20, 50, 100, 200. Suppose I had 200/1=200 of the 1s, 200/2 = 100 of the 2s, 200/5 of the 5s, etc. I could then take any number of my 1s, along with any number of my 2s, etc, see how much I have, and see if the total is 200. So I’ve got a product space [0,200/1]\times [0,200/2]\times [0,200/5]\times\cdots\times [0,200/200] of possible combinations, and I want to pick out all those that have a value of 200. This presents a fun application of the map/reduce functions, which I can’t seem to get enough of.

Suppose I start with the list of coins available, [1,2,5,10,20,50,100,200], and my target value in mind. I want to replace each item in this list, say the value c, with the list of values I could make using only $c$-valued coins (and only enough to get to 200). I’m going to do something a little silly, and store each value as it’s own list (this’ll make the next step easier, I think). So I first do

target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]
var = map(lambda c: [ [v] for v in xrange(0,target+1,c)], coins)

Next, I want to make the cartesian product of all of these list of lists. I’ll build up my product, working my way through var. That is, I think about L_1\times L_2\times \cdots \times L_k as (((L_1\times L_2)\times L_3)\times \cdots )\times L_k, where each L_i here is a list. This is the sort of thing reduce is for. Keeping in mind that all of my lists are lists of one-element lists (so “+” below is really “concatenate”), I can build the cartesian product via

var = reduce(lambda l,r: [ x+y for x in l for y in r ], var)

Now each element of var is a list with as many values as there are coins, e.g. [7, 6, 0, 40] corresponds to 7 in 1s, 6 in 2s, 0 in 5s, 40 in 10s (of course, in the running example, I need more values in the list, but I hope the point comes across). To find the combined value of the coins in each list, I just need the sum, so I do

var = map(sum, var)

Finally, I only want the values where the sum is my target value, so I filter. We’re asked for the number of ways to make the target value, so I take the length:

var = filter(lambda t: t == target, var)
print len(var)

This is not particularly efficient. In the stated problem, the product of my lists has 1.28 billion elements (significantly larger than the actual answer, which is less than 100,000). That’s rather a lot of space to be taking up. I tried running this code on a target value of 100, and gave up on it after about 20 minutes. For contrast, the first solution above, the recursive solution, takes about half a second on my computer. Still, I like this exercise of getting the cartesian product of a bunch of lists.

Problem 30 – Sums of Digit Powers

October 1, 2009

In problem 30 we are asked to find all the numbers that are the sum of the n-th powers of their digits. Well, the sum of those numbers. And n=5. You can just about do it in one line…

Most of this problem is fairly easy: Given a number, compute the sum of the powers of its digits, and see if you get the number you started with. If you wanna find all such numbers, just loop for a while. The trouble is how long? If you’ve got some range in mind you want to look at, you can do the following:

def solve(pow, low, hi):
    """ Find the sum of all numbers that are the sum of their pow-th powers of digits in the interval [low,hi) """
    return sum(filter(lambda n:n==sum(map(lambda d:int(d)**pow,str(n))) xrange(low, hi)))

Ok, sure, it’s a longish line, but it’s all there. Python’s syntactic sugar for handling all the little looping is awesome.

The remaining trick is to figure out those bounds. The problem mentions not using 1 as one of the numbers, so we could start at 2. However, that means we could start at 2**pow, because that’ll be the lowest digit sum we’d make. On the high end, the biggest digit-power-sum will come from digits being 9. So I figure that to find an upper bound, you can think about digit sums for longer and longer strings of 9. If you think about k 9s in a row, that’ll give a digit sum of k\cdot 9^p (if p is the specified power). Find the largest k where this value is still a k-digit number (or bigger), and you’ve got yourself an upper bound to loop to. Here’s some code to find the bound:

def bound(pow):
    """ Find bound on nums that can be sum of their pow-th powers of digits """
    if pow <= 1:
        return 9
    nine = 9**pow
    coeff = 1
    while(len(str(coeff*nine)) >= coeff):
        coeff += 1
    return (coeff - 1)*nine

Now, these bounds I’ve set up are pretty poor. In the case where the power is 4, as in the example problem, we’d loop from 2**4=16 to 32805, when the actual numbers that have the property we’re hoping for are between 1000 and 10000. We’ve overshot by something like 3 times too many values.

So, we could try to be more clever and come up with a smaller set to search in. But we could still use that one-line solver to pick from that set the appropriate values. And that makes me happy.