## Problem

The fraction $\frac{49}{98}$ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that $\frac{49}{98}=\frac{4}{8}$, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like $\frac{30}{50}=\frac{3}{5}$ to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

## Solution in Python

We really only need to iterate from 10 to 99 for the numberator and from the numerator to 99 for the denominator, since we require that the fraction be less than one. Also, we can ignore any denominators that have zeros (since the only other possible integer to match in the numerator is nonzero). We form a list from the numerator and denominator, check for redundancy, remove the redundancies when found, then cross multiply to find if the fractions are equivalent to their redundant-removed siblings.

import time import fractions   start = time.time()   p = fractions.Fraction(1,1)   for a in range(10, 100, 1): for b in range(a+1, 100, 1): if b % 10 == 0 or a == b: continue La, Lb = [a/10, a%10], [b/10, b%10] if any(i in Lb for i in La) and not all(i in Lb for i in La): if La[0] in Lb: x = La[0] else: x = La[1] La.remove(x) Lb.remove(x) if a*Lb[0] == b*La[0]: p *= fractions.Fraction(La[0],Lb[0])   elapsed = time.time() - start   print "result %s found in %s seconds" % (p, elapsed)

We’ve used Python’s fractions module to make things a bit easier. When executed, we get the following.

result 1/100 found in 0.00531482696533 seconds

### One Comment

1. Slimfast
Posted October 30, 2016 at 08:31 |

some small changes will make it even faster, I think:

for a in range(10, 100, 1)
–> for a in range(11, 100, 1)

if b % 10 == 0 or a == b: continue
–> if (b or a) % 10 == 0 or a == b: continue

if any(i in Lb for i in La) and not all(i in Lb for i in La):
–> if any(i in Lb for i in La):

indeed, given the previous restriction, with “a==b”, the second part of the “and” is redundant