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

Written by on 26 March 2011

Topics: Project Euler

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.

8 Comments For This Post I'd Love to Hear Yours!

  1. Avidan says:

    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 ‘<'

  2. Avidan says:

    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

  3. Avidan says:

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

  4. Kristian says:

    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

  5. shubham says:

    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?

  6. Kristian says:

    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.

  7. james porcelli says:

    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.”

  8. Mathijs Frenken says:

    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?

Trackbacks For This Post

  1. Project Euler Digit Cancelling Fractions Solution | The Daily Programmer

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.