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.

### Like this:

Like Loading...

*Related*

Tags: prob33

This entry was posted on October 30, 2009 at 11:31 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply