Problem 33 — Digit Cancelling Fractions

solved Tue, 12 Nov 2019, 15:14 · level 0 · difficulty 2% projecteuler.net github

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

We shall consider fractions like, $30/50 = 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.


Problem Analysis

The puzzle asks for two-digit fractions n/d below one in value where a naive "cancellation" of a digit shared between numerator and denominator happens, by coincidence, to give the correct reduced fraction. The canonical example is 49/98 = 4/8: cancel the shared 9 and the equation still holds. To pin this down algebraically, I write the numerator with digits a and x (value 10a + x) and the denominator with digits x and b (value 10x + b), so the shared digit x sits at the end of the numerator and the start of the denominator. Cancelling x leaves a/b, and I want exactly those triples where (10a + x) / (10x + b) = a / b. The problem excludes "trivial" cases such as 30/50 = 3/5, where x = 0 merely strips a factor of ten from both numbers; I enforce this by requiring x to be a genuine nonzero digit distinct from both a and b.

The decisive observation is that I must never test this equality in floating point. Comparing two fractions p/q = r/s is equivalent to comparing the integers p*s and r*q - a technique called cross-multiplication. Applied here it yields the exact integer test (10a + x) * b = (10x + b) * a, which sidesteps rounding error entirely. The search space is tiny: a from 1 to 9, b strictly greater than a (so the fraction stays below one), and the shared digit x from 1 to 9 distinct from both. That is at most a few hundred triples, so a brute-force search finishes instantly. Once the four qualifying fractions are found I multiply them and reduce the product to lowest terms; the answer is the resulting denominator. The whole computation is O(1) - a bounded, constant-size enumeration.

Solution Approach

Algebraic Digit Enumeration (Python and C)

Both files implement one algorithm. I iterate the single-digit denominator from 2 to 9, the single-digit numerator from 1 up to (but not including) the denominator - which guarantees the fraction is less than one - and the shared digit x from 1 to 9. I skip any x equal to the numerator or denominator, because those would either be the trivial cancellation or a degenerate match. For the surviving triples I apply the cross-multiplied test (10 * numerator + x) * denominator == (10 * x + denominator) * numerator. Each match contributes one fraction to a running product.

The Python version expresses the whole search as a single generator expression feeding functools.reduce. Each matching triple is materialised as a fractions.Fraction, and the fold multiplies them together starting from the identity Fraction(1, 1). Because Fraction keeps every intermediate result in lowest terms automatically, the final answer is simply the .denominator attribute of the product. I chose this representation because it removes any chance of an arithmetic bug in the reduction step - the standard library does the work.

The C version has no rational type, so I instead accumulate the product of all matching numerators in one variable and the product of all matching denominators in another, then reduce the pair at the end. The reduction uses Euclid's algorithm to compute the greatest common divisor of the two products, and the answer is den_product / gcd. The two implementations are mathematically identical; the C version just makes the accumulation and reduction explicit rather than hiding them behind a library type.

workbench

Test cases

categoryinputanswer
main 100

Results

solutioncategoryanswerverdict avg seconds cavg seconds py
p0033_s0 main 100 correct 0.000001 (63) 0.000025 (63)

Files

Tags & blogs

Blogs