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

    >>> simplify_bad(49, 98)
    (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


def is_curious_fraction(x: int, y: int, x_bad: int, y_bad: int) -> bool:
    """ 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
    """

    if x_bad == x:
        return False  # no cancellation occurred, cannot be "curious"
    elif y_bad == 0:
        return False  # cancellation resulted in invalid fraction
    else:
        return x_bad / y_bad == x / y


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):
            numerator_cancelled, denominator_cancelled = simplify_bad(numerator, denominator)
            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
    return answer


expected_answer = 100

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

Return type:

bool

Returns:

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

Return type:

Tuple[int, int]

Returns:

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