Detailed mathematical approach

Problem Summary

We look at proper fractions built from two-digit integers, so the numerator and denominator have the form \(10a+b\) and \(10c+d\) with \(1 \le a,c \le 9\) and \(0 \le b,d \le 9\). A fraction is interesting if cancelling one common digit by a mathematically invalid shortcut still leaves an equal fraction. The classic example is \(\frac{49}{98}=\frac{4}{8}\) after cancelling the 9s.

The problem asks for every non-trivial example of this phenomenon with numerator smaller than denominator, excluding the obvious zero-ending cases such as \(\frac{30}{50}\). After finding all such fractions, we multiply them and reduce the product to lowest terms; the required output is the denominator of that reduced product.

Mathematical Approach

The three implementations all work by testing every two-digit proper fraction, but the search is guided by a small amount of algebra. Writing the digits explicitly shows exactly which cancellations are possible and which ones can never produce a genuine solution.

Encoding the numerator and denominator

Write

$N=10a+b,\qquad D=10c+d,\qquad N \lt D,$

with \(a\) and \(c\) non-zero because \(N\) and \(D\) are two-digit numbers. A digit-cancelling step can only happen when one digit in the numerator equals one digit in the denominator. There are four positional patterns:

$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$

After cancellation, the remaining one-digit fraction is respectively \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\), or \(\frac{a}{c}\). The implementation checks all four.

Two cancellation patterns are impossible for proper fractions

If the common digit sits in the tens place of both numbers, then

$\frac{10a+b}{10a+d}=\frac{b}{d}$

implies

$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$

Because \(a \neq 0\), we must have \(d=b\), so \(10a+b=10a+d\). That makes the original fraction equal to 1, which contradicts \(N \lt D\).

If the common digit sits in the units place of both numbers, then

$\frac{10a+b}{10c+b}=\frac{a}{c}$

gives

$c(10a+b)=a(10c+b)\implies b(c-a)=0.$

For a non-trivial cancellation the cancelled digit is not zero, so \(b \neq 0\), forcing \(a=c\). Again numerator and denominator are equal, so there is no proper fraction. Therefore only the mixed-position cancellations can matter.

The two mixed-position equations

When the numerator's tens digit matches the denominator's units digit, \(a=d\), the cancellation rule would claim

$\frac{10a+b}{10c+a}=\frac{b}{c}.$

Cross-multiplication gives

$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$

So any valid example in this branch must make \(a=\frac{9bc}{10c-b}\) a digit from 1 to 9.

When the numerator's units digit matches the denominator's tens digit, \(b=c\), the cancellation rule becomes

$\frac{10a+b}{10b+d}=\frac{a}{d},$

and cross-multiplication yields

$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$

Equivalently,

$d=\frac{10ab}{9a+b}.$

This is the branch that produces all genuine solutions in the two-digit problem.

Worked example and the full solution set

Take \(a=4\) and \(b=9\) in the \(b=c\) branch. Then

$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$

so we obtain

$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$

Scanning the digit range \(1\) through \(9\) shows that the only non-trivial fractions are

$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$

The mixed case \(a=d\) produces no additional examples, so these four are the complete set.

Multiplying the four fractions

It is easiest to multiply the simplified forms:

$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$

So after reduction to lowest terms, the denominator is \(100\). The implementations do not hard-code this fact; they multiply the original fractions they find and then reduce the final product with a greatest-common-divisor computation.

How the Code Works

The C++, Python, and Java implementations all follow the same constant-space exhaustive search. They use integer arithmetic throughout, so no floating-point comparison is needed anywhere.

Enumerating candidate fractions

The implementation loops over every two-digit numerator and every larger two-digit denominator. Restricting to \(N \lt D\) automatically limits the search to proper fractions and prevents counting a solution twice in reversed order.

Testing the four digit-sharing patterns

For each candidate, the two decimal digits of the numerator and denominator are extracted. The trivial case where both numbers end in zero is rejected immediately. Then the implementation checks the four possible ways a shared digit could line up: tens with tens, tens with units, units with tens, and units with units.

Whenever one pattern applies and the cancelled denominator digit is non-zero, the equality test is performed by cross-multiplication:

$N \cdot D' = D \cdot N'.$

This exactly matches the algebra above and avoids any rounding issues.

Accumulating and reducing the product

Every qualifying fraction contributes its original numerator and denominator to a running product. After the full sweep, the combined numerator and denominator are divided by their greatest common divisor. The denominator of that reduced product is returned as the answer. The C++ and Java versions also include small sanity checks that confirm \(\frac{49}{98}\) is accepted while \(\frac{30}{50}\) is rejected.

Complexity Analysis

There are only \(90\) two-digit numbers, so the number of candidate proper fractions is

$\binom{90}{2}=4005.$

Each candidate requires a fixed amount of work: digit extraction, up to four pattern tests, and a few integer multiplications. The final GCD is also constant time for numbers of this size. Therefore the running time is \(O(1)\) for the actual Project Euler input, or \(O(R^2)\) if one imagines extending the same idea to all numbers below a bound \(R\). The space usage is \(O(1)\).

Footnotes and References

1. Problem page: Project Euler 33
2. Digit-cancelling curiosities: Wikipedia - Anomalous cancellation
3. Cross-multiplication for fraction equality: Wikipedia - Cross-multiplication
4. Greatest common divisor and Euclid's algorithm: Wikipedia - Greatest common divisor