# Project Euler Problem 33: Digit Cancelling Fractions¶

The source code for this problem can be found here.

## Problem Statement¶

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 $$9\mbox{s}$$.

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 Discussion¶

Nothing special here, just implement the faulty cancelling logic and see when it just so happens to agree with the correct arithmetic results. Accumulate these so-called curious fractions.

## Solution Implementation¶

from fractions import Fraction
from typing import Tuple

from lib.digital import digits_of, digits_to_num

def simplify_bad(a: int, b: int) -> Tuple[int, int]:
""" Simplify the fraction :math:\\frac{a}{b} using the incorrect logic specified for this problem

In particular, individual decimal digits are directly cancelled with each other rather than considering common
divisors of :math:a and :math:b.

:param a: fraction numerator
:param b: fraction denominator
:return: the simplified fraction :math:\\frac{a}{b} using the incorrect logic

(4, 8)
"""

# Get the decimal digits of the numerator and denominator
a_digits = digits_of(a, base=10)
b_digits = digits_of(b, base=10)

# Build copies of the digits and start cancel them out if possible
aa = a_digits.copy()
bb = b_digits.copy()
for a_i in a_digits:
if a_i in bb and a_i != 0:
aa.remove(a_i)
bb.remove(a_i)

return digits_to_num(aa), digits_to_num(bb)  # convert the remaining digits back to integers

""" Test to see if :math:\\frac{x}{y} is a "curious fraction"

:param x: the numerator of the fraction
:param y: the denominator of the fraction
:param x_bad: the numerator of the (incorrectly) cancelled fraction
:param y_bad: the denominator of the (incorrectly) cancelled fraction
:return: whether :math:\\frac{x}{y} is a "curious fraction" or not
"""

return False  # no cancellation occurred, cannot be "curious"
return False  # cancellation resulted in invalid fraction
else:

def solve():
""" Compute the answer to Project Euler's problem #33 """

n_digits = 2  # number of digits in each numerator/denominator
curious_product = Fraction(1, 1)  # will accumulate the product of curious fractions

for numerator in range(10 ** (n_digits - 1), 10 ** n_digits):
for denominator in range(numerator + 1, 10 ** n_digits):
if is_curious_fraction(numerator, denominator, numerator_cancelled, denominator_cancelled):
curious_product *= Fraction(numerator_cancelled, denominator_cancelled)

answer = curious_product.denominator  # extract the denominator from the simplified fraction


solutions.problem33.is_curious_fraction(x, y, x_bad, y_bad)

Test to see if $$\frac{x}{y}$$ is a “curious fraction”

Parameters: x (int) – the numerator of the fraction y (int) – the denominator of the fraction x_bad (int) – the numerator of the (incorrectly) cancelled fraction y_bad (int) – the denominator of the (incorrectly) cancelled fraction bool whether $$\frac{x}{y}$$ is a “curious fraction” or not
solutions.problem33.simplify_bad(a, b)

Simplify the fraction $$\frac{a}{b}$$ using the incorrect logic specified for this problem

In particular, individual decimal digits are directly cancelled with each other rather than considering common divisors of $$a$$ and $$b$$.

Parameters: a (int) – fraction numerator b (int) – fraction denominator Tuple[int, int] the simplified fraction $$\frac{a}{b}$$ using the incorrect logic
>>> simplify_bad(49, 98)
(4, 8)

solutions.problem33.solve()

Compute the answer to Project Euler’s problem #33