Euleryx Problem 25 – 1000-Digit Fibonacci Number
My workflow:
Spoiler
Workflow:
Answer: 4782
Last Week's Favourite Solution:
Last weeks problem was, in my opinion, one of the most challenging problems yet. I really enjoyed looking through all the solutions however, the favourite solution award goes to @Hub119 . Leveraging the generate rows and multifield formulas in a very clever way, lead to a solution which ran in under a second. Its hard to explain the trick used without giving spoilers, but if you're interested, please view the spoiler tab below, or find the solution on page one of last week's post or click here.
Spoiler
The two pieces which stood out to me most were firstly, the use of the generate rows, to help avoid the need for an iterative approach, and secondly, was the get part function.
In the screenshot below, you can see that it's possible to calculate the “position ID” of the number you require (column “a”). The difficulty is that after you remove a number, the list is then updated, meaning lots of the numbers now have a different position ID. Below, you can see a series of multirow, in which the GetPart() function was used, to update the list of remaining numbers, each time one had been selected. It was both a clever solution and I also learned about a new Alteryx function!
(Note: Credit to @Hub119 for the solution pictured below)
Mathematical Theory:
We first saw the Fibonacci sequence back in Project 2 where we looked at approximating the sequence, to help us generate only the necessary terms. For this challenge we will once again be using an approximation to help arrive at an answer.
A common formula used to approximate the terms of the Fibonacci sequence is:
Where n represents the index of the term you are calculating. To check this formula is a good approximation we can calculate the first few terms and compare them to the exact value.
As you can see, the values align pretty closely, suggesting that our formula is a good approximation.
Now we have a formula to approximate a given term, we need to find the value for n, where the answer first exceeds 1000 digits. The smallest 1000 digit number will be 10 to the power of 999. Doing a quick sense check, we know this to be true as 10 squared (10^2) has 3 digits, 10 cubed (10^3) has 4 digits etc…
Writing this new information into an equality we conclude that the approximate value for a Fibonacci number will exceed 1000 digits when the following holds:
The only unknown value here is n. We could just trial different values of n, and we would indeed arrive at a solution, however, we would be dealing with 1,000 digit numbers which as we already know, require more complex computation methods, as they exceed the max size of an int 64. Instead I decided to try and rearrange the above equation.
This did require the use of logarithmic functions and some rules commonly referred to as the Laws of Logs. Whilst you can see the relevant laws listed below, if you are interested in looking into the derivations, I encourage you to look at the following resource (Derivation – Rules for Logarithms). For anyone unaware of what logarithmic functions are, the easiest way to descript them, is as the opposite to a power/exponent, i.e
We know that:
So the equivalent log function would be
In other words, the log part reads as, how many times do you multiply 10 by itself, to get 10,000. Generalising this we get the following two equations:
As for the logarithmic rules mentioned earlier, the ones I will be using are as follows:
(source: chillimath.com)
Now for the actual rearrangement:
Step one, is to log, both sides:
Step two, implement, rule 2:
Step three, implement rule 3:
Step four, add the second argument to both sides:
Step five, isolate n by dividing both sides by the other remaining term on the left-hand side:
Now, all that’s left is to plug this into a calculator, resulting in:
As we know n has to be a whole number (as you cant have half a term in a sequence), the answer is found by rounding up to the nearest integer.
Method:
1) This week we have been able to do the heavy lifting via the mathematical methodology above, however that doesn’t mean we should forget basic design principals. Alteryx is an incredibly versatile tool, and we should take advantage of this by building dynamic workflows where possible. My input is the number of digits we are after (in this case 1,000).
2) To arrive at the answer the only step remaining is to implement the formula we derived above.
3) Submit your answer to the Project Euler Website!
Summary:
Obviously, an exact value is always preferred to an approximation, however this problem helps prove how approximations can still be sufficient. By using a formula which approximates the terms in the Fibonacci sequence we were able to arrive at an answer with both minimal build, and run time.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
