49/98 = 4/8 if you cancel the 9s. This happens for few others fractions where , and we’ll also ignore for digits . 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.

Advertisements