Archive for October 30th, 2009

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.