Euleryx Problem 33 – Digit Cancelling Fractions
My workflow:
Spoiler
Workflow:
Answer: 100
Last Week's Favourite Solution:
Several different interesting approaches to last week's challenge, especially within the generate rows and filter tools. The winner of Last Week's Favourite solution is @AncientPandaman , for not only winning on the tool golf front and providing a smart conditional format in the generate rows, but also for the filter technique used to detect which records had all digits 1-9. Whilst I don't want to give too much away, I will say the function is actually a relativley common one, just not typically in this context. Please find their solution on page one of last week's post or click here.
Definitions:
- Curious Fractions: A fraction where incorrectly cancelling a shared digit between the numerator and denominator happens to give the correct simplified answer. For example, in the fraction 49/98, cancelling the 9s gives 4/8, which is equal in value to the original fraction.
Please Note: Due to being away, next week's episode will be delayed, but fear not, the next problem will be released on the 16th April!
Mathematical Theory:
The problem asks us to find all two digit fractions, less than one in value, where incorrectly cancelling a digit shared between the numerator and denominator gives the correct result (curious fractions).
For any two digit fraction, we can represent the numerator as a two digit number with digits A and B (AB, as in two digits, not multiplication) and the denominator as a two digit number with digits C and D (CD). This would make the overall fraction: AB/CD
There are then four possible ways the digits could be cancelled:
- A = C (first digits match), leaving B/D
- A = D (first digit of numerator matches second digit of denominator), leaving B/C
- B = C (second digit of numerator matches first digit of denominator), leaving A/D
- B = D (second digits match), leaving A/C
For each of these scenarios, we check whether the cancelled fraction equals the original. The approach taken in this workflow is to generate all possible two digit fractions, perform each type of cancellation, and filter to only those where the values match.
Once all four curious fractions have been identified, the problem asks us to multiply them together and identify the denominator when the fraction is expressed in its simplest form.
To find the simplest denominator, the workflow uses a neat trick. Let's take 0.4 as an example.
First, consider the number divided by 1, it will, of course, just equal itself.
0.4/1 = 0.4
This is effectively the fraction we are after, we just need to express it using integers. The next step is to find the reciprocal, which puts the original denominator on top, and the numerator on the bottom.
1/0.4 = 2.5
Now 2.5 still isn’t an integer, but what we can do is multiply both sides by 2, to get
2/0.4 = 5
If a fraction still remained, then we could try multiplying by 3, and so on, until we got an integer. In this case, we already have a solution and a simple rearrangement will produce:
2/5 = 0.4
Which is correct and in its simplest form. So by finding the reciprocal, then multiplying by increasing values, until an integer is reached, we can identify a fraction in its simplest form.
Method:
1) The first step is to input all whole numbers from 11 to 99. These will serve as both the potential numerators and denominators for our two-digit fractions.
2) Append the list of numbers onto itself to create every possible two-digit fraction combination. Then, filter out any fractions which are greater than or equal to 1, and remove any trivial solutions (where the numerator/denominator ends in 0).
3) For each remaining fraction, cancel out the shared digits between the numerator and denominator. Then calculate the value of both the original fraction and the new cancelled fraction.
4) Filter to only those records where the two values are equal. These are the curious fractions.
5) Find the product of all the curious fractions. This is done by multiplying the numerators together and the denominators together, giving us a single fraction representing the product.
6) Using the technique mentioned in the theory section, by first identifying the reciprocal, use the generate rows to calculate the denominator for the fraction in its simplest form.
7) Submit your answer to the Project Euler Website!
Summary:
By generating all possible two digit fractions and checking which ones satisfy the curious property, we were able to identify the four fractions without needing any complex algorithms. Although the answer didn’t need any complex logic for identifying the lowest possible denominator, arguably, the key was figuring out how to do this dynamically.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
