Project Euler 33: Discover all the fractions with an unorthodox cancelling method

Problem 33 of Project Euler is a really fun little problem.  At least I think so. It reads

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 9s.

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.

The problem itself is rather easy to solve using brute force since there are less than 90*90 = 8100 possible solutions we would have to check. Each check is fairly easy to perform and thus we would be able to brute force comfortably within the 1 minute range.

Limiting possible solutions

However a few things can be said about the problem with mathematics, and in order for this post to be inspirational I will dive a bit into that.

We are looking for fractions where there is at least one common digit in both the nominator and the denominator which can be removed. That gives us four combinations for equations which could give us a solution.

Lets define the following nominator and denominator where and the variable we want to cancel where . Such that we have 3 integers between 1 and 9 where d is larger than n such that we ensure that we have a proper fraction (less than 1).

There is a total of four combinations which can yield a set of i‘s that can be cancelled. These are

1)

2)

3)

4)

Lets treat them one by one to find their properties and possible solution space.

1)

Which is impossible due to the definition that n < d.

2)

Same argument as 1).

Since d > n the right hand side is positive, so in order to have a solution the left hand side must be positive as well and therefore n > i. Rearranging a bit more

The left hand side is larger than or equal to 1 due to the result from above on n and i. However, since i < 9 first part of the right hand side is smaller than 1 and subtracting something from it is not going to make it larger. Therefore this equation has no solutions.

Since the problem states that there are four solutions to the problem, all of them must be in in the form 4), which the example also fits into.  Rewriting it

From the definition the right hand side is negative and therefore the left hand side must also be negative leading to n < d < i.

Writing the code

In the previous section we discovered that all solutions will have the form

And all the solutions adhere to n<d<i. That should enable us to write a piece of code that only checks very few equations.

One note before implementing it. I personally don’t like to work in doubles for a problem like that, so instead of checking if fractions are equal I have rewritten the check so say that we have a solution is . That means we can keep everything in integers.

The implementation in C# looks like

int denproduct = 1;
int nomproduct = 1;

for (int i = 1; i < 10; i++) {
    for (int den = 1; den < i; den++) {
        for (int nom = 1; nom < den; nom++) {
            if ((nom * 10 + i) * den == nom * (i * 10 + den)) {
                denproduct *= den;
                nomproduct *= nom;
            }
        }
    }
}

It needs to check a total of 84 different solutions, that’s fairly slick. Now we only need one more thing. The three loops are implemented with bounds according to the formula we derived above. All we need to do to answer the question is to reduce the resulting fraction to the lowest common terms. For that we can divide the denominator with the greatest common divisor. We implemented a method to calculate it in Problem 9. So take a look at the solution for that or peek in the source code.

We just need to add one line of code to get the result

denproduct /= gcd(nomproduct, denproduct);

and we are done.

Wrapping up

We have not found a solution method for the problem of finding the fractions where an unorthodox cancelling method would work. As I mentioned in the beginning of the post, it should be pretty easy to brute force the problem and therefore I don’t wouldn’t expect to see much of a timing issue.

Running the code gives us the result

The product of denominators 100
Solution took 0 ms

I have linked to it earlier, but you can of course find the source code for download here. Once again I would like to encourage you to give comments, other solutions, correct mistakes and so on.

Posted by Kristian

10 comments

I solved it without programming. Start with your last equation:
9n(d – i) = i(n – d)
Rearrange it a bit more
9n(i – d) = i(d – n)
n(i – d) = i(d – n) / 9

For i(d – n) to be divisible by 9, i could be 3, 6 or 9. Check each one:

if i = 3, d – n can be 3 or 6. That’s impossible because n < d < i (n < d < 3). The only possible values are n = 1, d = 2, and they are incorrect.
if i = 6, d – n can be 3 or 6. d – n can't be 6, because d < n < i (d < n < 6). So d – n has to be 3. Possible solutions are (n = 1, d = 4), (n = 2, d = 5).
if i = 9, we get

n(9 – d) = 9(d – n) / 9
9n – nd = d – n
10n – nd = d
n(10 – d) = d
n = d / (10 – d)

For n to be positive d has to be 5 <= b 9 first part of the …”. I think you meant ‘<'

The rest of my post was cancelled for some reason 🙁

For n to be positive d has to be 5 <= b <= 9.
The only possible values of d from 5 to 9, where d / (10 – d) is an integer are d = 5 (n = 1), d = 8 (n = 4).
So possible solutions for i = 9 are (n = 1, d = 5), (n = 4, d = 8)

We can now collect all of our possible solutions and see that each of them is correct.

(n = 1, d = 4, i = 6)
(n = 2, d = 5, i = 6)
(n = 1, d = 5, i = 9)
(n = 4, d = 8, i = 9)

Hence, the fractions are:

16/64 = 1/4
26/65 = 2/5
19/95 = 1/5
49/98 = 4/8

B.T.W I think you have a typo in “… However, since i > 9 first part of the …”. I think you meant ‘<'

Nice solution. Thanks for sharing that with us, I see now that it didn’t take many calculations to deduce the rest by hand. I just couldn’t see it when I solved the problem.

And yes you are right, it was a typo, which is now fixed

I am curious to know why there would be only four fractions.
if we take 46/67 = 4/7 (<1) but it doesnt satisfy n<d<i property
49/95 = 4/5 (<1) and it satisfies the property n<d<i

but all these fractions is not being considered here while it satisfies the problem statement?

I am not sure what you are referering to. I think the first one you mention is covered by fraction 4 and in fact it is the only one that can possibly have any candidates.

[…] Solution: When we initially saw this problem, we wanted to brute force the small solution space and take the easy win. But we realized that wouldn’t help us improve as programmers or thinkers. We instead decided to try to eliminate possible solutions to add some fun to the problem. The total number of possible solutions we checked was 628 — which is a lot less than the 4005 possible solutions but not quite as good as the 84 achieved over on the Math Blog. […]

james porcelli

Can you describe how you realized “There is a total of four combinations which can yield a set of i‘s that can be cancelled.”

Mathijs Frenken

Why do you use 10 in your calculations? Why not just d + i/n + i = n/d for example? Why do you use 10d + i/10n + i = n/d?

Leave a Reply