Problem 33

https://projecteuler.net/problem=33

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

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of faction, 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.

Notes

  • Point-1: There are 4 non-trivial examples.
  • Point-2: Less than one in value. That means numerator is less than the denominator.
  • Point-3: They contain two digits in the numerator and denominator.
  • Point-4: They are of the form ax/xb == a/b or xa/bx == a/b; where a, b, and x are digits 0-9.
  • Point-5: When in the ax/xb form, a<=x because of point 2, and when a==x, x<b.
  • Point-6: When in the xa/bx form,...
  • Point-7: There are only 3 unknown digits. We can brute force all 10^3 possibilities.

In [1]:
import math
def classify(a, b, x):
    if a == b:
        return None # trivial example
    a = float(a)
    b = float(b)
    x = float(x)
    if a > 0 and x > 0 and b > 0:
        n = a*10+x
        d = x*10+b
        if n < d and math.isclose(n/d, a/b):
            return 'ax/xb'
    if x > 0 and b > 0:
        n = x*10+a
        d = b*10+x
        if n < d and math.isclose(n/d, a/b):
            return 'xa/bx'
    return None

In [2]:
classify(4, 8, 9)


Out[2]:
'ax/xb'

In [3]:
classify(3, 5, 0)

In [4]:
import numpy as np
def find_curious_functions():
    for a in range(10):
        for b in range(10):
            for x in range(10):
                c = classify(a, b, x)
                if c is not None:
                    print('a={}, b={}, x={}, classification: {}'.format(
                        a, b, x, c))
                if c == 'ax/xb':
                    yield np.array([a*10+x, x*10+b])
                if x == 'xa/bx':
                    yield np.array([x*10+a, b*10+x])
curious_fractions = list(find_curious_functions())
curious_fractions


a=1, b=4, x=6, classification: ax/xb
a=1, b=5, x=9, classification: ax/xb
a=2, b=5, x=6, classification: ax/xb
a=4, b=8, x=9, classification: ax/xb
Out[4]:
[array([16, 64]), array([19, 95]), array([26, 65]), array([49, 98])]

In [5]:
v = np.array([1,1])
for i in curious_fractions:
    v *= i
v


Out[5]:
array([  387296, 38729600])

We could use GCD to simplify the fraction to its lowest common terms, but this is quite straightforward. The denominator is exactly 100 times the numerator. Therefore the answer is 100.