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 | Permalink

    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

One Trackback

  1. [...] is possible to solve this problem using less lines of code. Here is a link to a very short solution by Jason. Our aim however was not solve this in least lines of [...]

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">