Euleryx Problem 26 – Reciprocal Cycles
My workflow & macro:
Spoiler
Workflow:
Macro:
Answer: 983
Last Week's Favourite Solution:
Last week's project was possible through a formulaic approach however, @Qiu managed to create a brute force approach which ran in under 15 seconds! This was a well-optimised solution, which was able to quickly execute string addition to arrive at an answer, making it last weeks favourite solution! Please find the solution on page one of last week's post or click here.
Mathematical Theory:
This project centres around division, the main idea is to spot when a recursive pattern is about to occur. There are many ways to do this but I was taught long division using the “bus stop” method, which looked something like the below:
I wont explain the division itself, but just as a comment on this way of notating the calculation - you can see, as the divisor (6) was unable to go into 1, so the 1 was “carried forward” as a remainder of 10. This is denoted by adding the 1 in red, next to the 8.
Now for this challenge, we are dealing with reciprocals, so it will always be 1 divided by the value. The solution below is built aroudn spotting repetition in the "remainders" mentioned above, but its probebly best to show this via an example. Here's an example for 1/6 we start with:
Our remainder from the first iteration was 10. On the next step we get:
This time the remainder was 4. After taking one more pass, we get:
Again, the remainder was 4. Now we could continue to calculate more terms; however, as we have previously had a remainder of 4, we know exactly what will happen next. In fact, we know exactly what will happen in all subsequent steps. They will all yield a digit of 6, for the decimal and have a remainder of 4.
Instead of continuing to calculate these digits, we can recognise the fact that the remainder has been repeated, and stop the processing here, knowing that we have found a loop. This simple principle of spotting a repeated “remainder” when performing long division forms the basis of the solution below.
Method:
1) The first step is to generate our input data. I created a list of all numbers 1-1,000, set a numerator column equal to 1, then some placeholder columns, which would get populated later on. This data is then fed straight into the iterative process.
2) The iterative macro is designed to calculate the next digit, for the decimal value. As discussed above, if the remainder (i.e the new numerator) is the same as one previously, seen, then we know there is a recursive sequence, so will let the record exit the macro. Equally, if an exact decimal is found, then the macro is exited too.
- The first step is to implement the formulas, which calculate the next digit (integer component), the remainder (which will become the numerator for the next iteration), and update the Decimal and Numerator list.
- Next, some of the original columns are dropped, and the remainder is renamed to “Numerator”. With these changes applied, any exact decimals (where the numerator = 0) are removed, as there is no point in passing them round again.
- The final step, is to join the lates numerator, back to the list of previous numerators for each number, to see if it has already occurred. By using a Text to Columns tool (set to split by rows), we can easily use a join tool to check this. If the record joins, it can be removed, otherwise it continues round for the next iteration.
3) Once out of the iterative, the data is filtered to remove the exact decimals (where the next numerator = 0).
4) The list of numerators is then parsed to allow one per row and set with a Record ID.
5) We can then find the record ID for the first and last time a given numerator appeared.
6) Subtracting these two values will give the length of the recursive sequence.
7) Sort descending and sample the top one to arrive at your answer!
8) Submit your answer to the Project Euler Website!
Summary:
Going back to the basics by looking at division forced us to look for patterns. The key to the solution above was to stop processing as soon as the pattern began to repeat itself.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
