Project Euler Problem 33

Project Euler Problem 33

Solution

Answer: 100

1. Mathematical analysis

We are looking for two-digit fractions less than 1 where an incorrect digit cancellation accidentally gives the correct simplified fraction.

Example:

$$\frac{49}{98} = \frac{4}{8}$$

The incorrect step is “canceling” the common digit $9$, yet it still happens to preserve the value.

We want:

• numerator and denominator are two-digit numbers
• fraction is less than 1
• non-trivial (exclude cases like $30/50 = 3/5$, where canceling zeros is obvious)
• exactly four such fractions exist

We must multiply those four fractions and reduce to lowest terms, then return the denominator.

Step 1: Represent the fraction

Let:

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

where:

• $a,b,c,d$ are digits $1$–$9$ (avoid trivial zero cases)
• numerator $<$ denominator

We seek fractions where canceling a shared digit incorrectly still works.

There are four cancellation patterns:

1. cancel $b=c$:

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

1. cancel $a=c$
2. cancel $b=d$
3. cancel $a=d$

Instead of deriving equations algebraically for every case, the cleanest approach is brute force over all two-digit fractions:

• Try all numerators from 10 to 99
• Try denominators greater than numerator
• Ignore trivial examples ending in zero
• For any shared digit, remove it once and compare values

Since there are only:

$$90 \times 90 = 8100$$

possibilities, brute force is tiny and guaranteed correct.

Step 2: Known examples

Checking manually:

$$\frac{16}{64}=\frac{1}{4}$$

(cancel 6)

$$\frac{19}{95}=\frac{1}{5}$$

(cancel 9)

$$\frac{26}{65}=\frac{2}{5}$$

(cancel 6)

$$\frac{49}{98}=\frac{4}{8}$$

(cancel 9)

Multiply them:

$$\frac{16}{64} \cdot \frac{19}{95} \cdot \frac{26}{65} \cdot \frac{49}{98}$$

Simplify each:

$$= \frac14 \cdot \frac15 \cdot \frac25 \cdot \frac12$$

Numerator:

$$1 \cdot 1 \cdot 2 \cdot 1 = 2$$

Denominator:

$$4 \cdot 5 \cdot 5 \cdot 2 = 200$$

Thus:

$$\frac{2}{200}=\frac{1}{100}$$

So the denominator is likely 100.

---

2. Python implementation

from fractions import Fraction

# Store the product of all curious fractions
product = Fraction(1, 1)

# Search all two-digit numerator/denominator pairs
for numerator in range(10, 100):
    for denominator in range(numerator + 1, 100):

        # Skip trivial examples ending in 0
        if numerator % 10 == 0 and denominator % 10 == 0:
            continue

        n_str = str(numerator)
        d_str = str(denominator)

        # Look for a common non-zero digit
        common_digits = set(n_str) & set(d_str)

        for digit in common_digits:
            if digit == '0':
                continue

            # Remove one occurrence of the common digit
            n_new = n_str.replace(digit, '', 1)
            d_new = d_str.replace(digit, '', 1)

            # Must still leave one digit each
            if not n_new or not d_new:
                continue

            # Convert to integers
            new_num = int(n_new)
            new_den = int(d_new)

            # Avoid division by zero
            if new_den == 0:
                continue

            # Check if incorrect cancellation is accidentally correct
            if Fraction(numerator, denominator) == Fraction(new_num, new_den):
                product *= Fraction(numerator, denominator)

# Denominator of product in lowest terms
print(product.denominator)

---

3. Code walkthrough

Fraction

from fractions import Fraction

Using Python’s Fraction class avoids floating-point errors and automatically reduces fractions.

---

Initialize product

product = Fraction(1, 1)

We multiply all curious fractions into this accumulator.

---

Enumerate fractions

for numerator in range(10, 100):
    for denominator in range(numerator + 1, 100):

Checks every proper fraction:

$$\text{numerator} < \text{denominator}$$

with two-digit numbers.

---

Skip trivial cases

if numerator % 10 == 0 and denominator % 10 == 0:
    continue

Excludes examples like:

$$30/50 = 3/5$$

which are declared trivial.

---

Find shared digits

common_digits = set(n_str) & set(d_str)

If numerator and denominator share a digit, try canceling it.

---

Remove the digit

n_new = n_str.replace(digit, '', 1)
d_new = d_str.replace(digit, '', 1)

Removes exactly one occurrence of the shared digit.

Example:

"49" -> "4"
"98" -> "8"

---

Verify the equality

if Fraction(numerator, denominator) == Fraction(new_num, new_den):

Checks whether the mistaken cancellation still preserves the fraction’s value.

The program finds exactly:

$$\frac{16}{64}, \frac{19}{95}, \frac{26}{65}, \frac{49}{98}$$

Their product simplifies to:

$$\frac{1}{100}$$

---

4. Final verification

• Exactly four non-trivial fractions exist ✔️
• Product reduces cleanly to lowest terms ✔️
• Denominator is reasonable in size and matches known Project Euler behavior ✔️

Answer: 100