notes.html

problem 33 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
The puzzle asks for two-digit fractions <code>n/d</code> 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 <code>49/98 = 4/8</code>: cancel the shared <code>9</code> and the equation still holds. To pin this down algebraically, I write the numerator with digits <code>a</code> and <code>x</code> (value <code>10a + x</code>) and the denominator with digits <code>x</code> and <code>b</code> (value <code>10x + b</code>), so the shared digit <code>x</code> sits at the end of the numerator and the start of the denominator. Cancelling <code>x</code> leaves <code>a/b</code>, and I want exactly those triples where <code>(10a + x) / (10x + b) = a / b</code>. The problem excludes "trivial" cases such as <code>30/50 = 3/5</code>, where <code>x = 0</code> merely strips a factor of ten from both numbers; I enforce this by requiring <code>x</code> to be a genuine nonzero digit distinct from both <code>a</code> and <code>b</code>.
</p>
<p>
The decisive observation is that I must never test this equality in floating point. Comparing two fractions <code>p/q = r/s</code> is equivalent to comparing the integers <code>p*s</code> and <code>r*q</code> - a technique called <a class="reference-source" href="https://en.wikipedia.org/wiki/Cross-multiplication" rel="noopener noreferrer" target="_blank">cross-multiplication</a>. Applied here it yields the exact integer test <code>(10a + x) * b = (10x + b) * a</code>, which sidesteps rounding error entirely. The search space is tiny: <code>a</code> from 1 to 9, <code>b</code> strictly greater than <code>a</code> (so the fraction stays below one), and the shared digit <code>x</code> from 1 to 9 distinct from both. That is at most a few hundred triples, so a <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute-force search</a> 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(1)</a> - a bounded, constant-size enumeration.
</p>
<h3>Solution Approach</h3>
<h4>Algebraic Digit Enumeration (Python and C)</h4>
<p>
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 <code>x</code> from 1 to 9. I skip any <code>x</code> 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Cross-multiplication" rel="noopener noreferrer" target="_blank">cross-multiplied</a> test <code>(10 * numerator + x) * denominator == (10 * x + denominator) * numerator</code>. Each match contributes one fraction to a running product.
</p>
<p>
The Python version expresses the whole search as a single generator expression feeding <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.reduce" rel="noopener noreferrer" target="_blank">functools.reduce</a>. Each matching triple is materialised as a <a class="reference-source" href="https://docs.python.org/3/library/fractions.html" rel="noopener noreferrer" target="_blank">fractions.Fraction</a>, and the fold multiplies them together starting from the identity <code>Fraction(1, 1)</code>. Because <a class="reference-source" href="https://docs.python.org/3/library/fractions.html" rel="noopener noreferrer" target="_blank">Fraction</a> keeps every intermediate result in lowest terms automatically, the final answer is simply the <code>.denominator</code> 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.
</p>
<p>
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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="noopener noreferrer" target="_blank">Euclid's algorithm</a> to compute the <a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">greatest common divisor</a> of the two products, and the answer is <code>den_product / gcd</code>. The two implementations are mathematically identical; the C version just makes the accumulation and reduction explicit rather than hiding them behind a library type.
</p>
</article>