[C/C++] Project Euler #33 - Digit Cancelling Fractions

Project Euler #33 problem is about “Digit Cancelling Fractions.” This problem involves finding fractions where both the numerator and denominator are two-digit numbers and satisfy a specific condition. The condition is that when the numerator and denominator share the same digit, and this digit is “cancelled” in a simple way, the resulting fraction must still equal the original fraction.

For example, the fraction  \(\frac{49}{98}\)  is a special fraction. In this fraction, cancelling the digit 9 from both the numerator and the denominator gives  \(\frac{4}{8}\) . Since  \(\frac{49}{98}\)  and  \(\frac{4}{8}\)  have the same value, this fraction satisfies the condition. However, this method of cancelling digits is different from the normal way of reducing fractions (e.g., using the Euclidean algorithm) and focuses on the “digit cancellation” technique.

Cancelling digits in this way may seem like a simple trick, but since both the numerator and denominator must be two-digit numbers and the value of the fraction must remain unchanged after the digit is cancelled, the number of possible fractions is very limited.

The task is to find all four fractions that satisfy this condition, multiply them together, simplify the resulting product to its lowest terms, and then determine the denominator of this simplified fraction.

 

reduction of a fraction

This problem involves adding the same digit to both the numerator and the denominator of a fraction, such that the resulting fraction simplifies to the original fraction.

For a fraction  \(\frac{a}{b}\) , if the same digit 0 is added to both the numerator and the denominator at the end, it naturally results in the same value. Since this is a trivial solution, it must be excluded. To achieve this, a digit must be added to the numerator at the front and to the denominator at the back.

If a digit  x  is added to the front of the numerator and to the back of the denominator in a fraction  \(\frac{a}{b}\) , the equation becomes:

\[ \begin{align*}
a : b &= \frac{10x + a}{10b + x} \\
b(10x + a) &= a(10b + x) \\
x(10b - a) &= 9ab \\
x &= \frac{9ab}{10b - a} < a
\end{align*} \]



If the process is reversed, where  x  is added to the back of the numerator and to the front of the denominator, the equation becomes:

\[ \begin{align*}
a : b &= \frac{10a + x}{10x + b} \\
b(10a + x) &= a(10x + b) \\
x(10a - b) &= 9ab \\
x &= \frac{9ab}{10a - b} > b
\end{align*} \]

digit canceling fractions

The results can be obtained by simplifying the proportional equation through simple multiplication, so solving this problem should not be too difficult.

 

//------------------------------------------------
//    Project Euler #33 - Digit Cancelling Fractions
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n = 1, d = 1;
    for(int i = 2 ; i < 9 ; i++ )
    {
        for( int j = 1 ; j < i ; j++ )
        {
            for( int k = i+1 ; k < 10 ; k++ )
            {
                if( i*(j*10 + k) == j*(k*10+i) )
                    d *= k*10+i, n *= j*10+k;
                printf("%d %d %d\n", i, j, k);
            }
        }
    }

    int lcd = d;
    while( n )
    {
        int t = n;
        n = lcd%n;
        lcd = t;
    }
    printf("ans = %d\n", d/lcd);
}