General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 2 - Even Fibonacci Numbers
Here's my full workflow and Answer:
Answer: 4613732
Last Weeks Favourite Solution:
Just before we begin, there is something we must address first. It's been amazing to see so many different solutions posted to last weeks challenge already but as promised, we have chosen a favourite...
@gawa's 2 tool solution (text input + formula)! Thoroughly enjoyed reading the explanation and I always like a good Venn diagram too 😄. Find @gawa's solution on page 3 of last weeks challenge or click here.
Definitions:
- Fibonacci sequence: The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones
- Lower Bound: The smallest value a number or set of numbers can take. Put simply, a value which we know is less than or equal to the actual value we are interested in.
Mathematical Theory:
Firstly, it goes without saying that the Fibonacci sequence is one of the most famous sequences in mathematics. You may wonder why, or what makes it so important? The answer is simple; it appears everywhere!
Don’t believe me, here are just a few examples:
- Snail shells
- Sunflower seeds
- Other mathematical values (Golden ratio)
- Galaxy formation
- Many, many more
Now, moving on to lower bounds. For this problem, we need to find out all the terms up to and including the value 4,000,000. Sound simple, but how many terms is that? To help us come up with an estimate, let's look at an equation for a lower bound. I'm going to take the equation 1.5^n. Writing out the first few terms of this sequence, we get (rounded to 2 dp):
1.5, 2.25, 3.38, 5.06, 7.59, 11.39, 17.08
The first 7 terms of the Fibonacci sequence (starting at 1, 2) are
1, 2, 3, 5, 8, 13, 21
As you can see, after the 4th term, the sequence of 1.5^n is always smaller than the Fibonacci sequence. By definition, that makes it a lower bound for the Fibonacci sequence. It’s a bit like a guess that we know is wrong, but not too wrong.
As 1.5^n is a lower bound, we know that when 1.5^n > 4,000,000, the Fibonacci sequence will also be greater than 4,000,000 too.
By finding the smallest integer value of n, where the following is true, 1.5^n >= 4,000,000, we get the value n = 38. Therefore, if we find the first 38 terms of the Fibonacci sequence, we will definitely reach the 4,000,000 mark.
Method:
- Firstly, we must introduce the starting terms and set up the number of records we want to calculate. In this case, I know we will exceed 4,000,000 with 38 records, so I will generate this many records.
- Next, we must set up the starting table by combining the 38 term numbers with the first two terms. I have started with terms 0, 1 as this seems to be the modern standard; however, starting with 1,2 will achieve the same results.
(Note: I am aware the lower bound was calculated with 1, 2 as our initial terms; however, the same lower bound formula still holds for larger values of n, i.e 38) - Now let's implement the term-to-term rule, using a multi-row formula. (Don’t forget to set the Num rows value = 2).
- Filter to the even values under 4,000,000 and sum them.
- Submit your answer to Project Euler!
Summary:
Once you know the formula for the Fibonacci sequence, this problem is relatively easy to solve. However, thanks to lower bounds, we were able to minimise the required computations, without random guesswork!
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
These are fun to solve and learn new areas. My background is not in mathematics so these are really cool to learning new areas of the tool.
I went with the Generate Rows and Multi-Row tool method to get this answer.
Bacon
@BS_THE_ANALYST @caltang
I did some digging and found the sum of odd fibonnaccis and sum of even fibonnaccis below 4 million is not totally coincidence. 😁
The Fibonacci sequence, the pattern of odd and even numbers is: odd, odd, even, odd, odd, even, and so on, starting from 3.
This pattern arises because the sum of two odd numbers is always even, and the sum of an even and an odd number is always odd
The last 3 fibonnaccis below 4 million is happen to the one group of odd, odd, even.
And natually, the difference would be 1. 🤣
I solved simply.
Just catching up on Euleryx solutions - you all have some incredible solutions!
Got my tick:
I kept it simple - generate rows, multi-row formula to calculate Fibonacci numbers, filter and then summarize.
Found it interesting looking at other solutions to see why this is suboptimal. It runs in under a second but there's plenty of unnecessary calculation going on.
Thanks for the knowledge share, all!
