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.
No offense meant to @pilsworth-bulien-com, but the explanation of Fibonacci numbers sounded like the teacher in Charlie Brown to me, and it's only week 2! 😅
So I had chatty G explain it to me (literally asked to explain it as if you were explaining it to a non-mathematician/stat wizard and really dumb it down). And it worked! For me, at least. Here's the idea in layman's terms without mention of lower bounds.
🧠 What are Fibonacci numbers?
Think of it like a number recipe.
Start with two numbers:
1 and 1.
(Some versions start with 0 and 1, but we’ll stick with 1 and 1—it’s easier.)
Then, to get the next number, you add the last two numbers together.
So, it goes like this:
Start: 1, 1
Next: 1 + 1 = 2
Next: 1 + 2 = 3
Next: 2 + 3 = 5
Next: 3 + 5 = 8
Next: 5 + 8 = 13
Next: 8 + 13 = 21
Next: 13 + 21 = 34
Next: 21 + 34 = 55
... and so on.
So the Fibonacci sequence looks like this:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Each number is just the sum of the two before it. That’s the whole deal!
And here's my solution! It's not tool golf by any means, but hey - it looks pretty!
workflow
macroAlso this is the second iterative macro I've made in two days.....very usual for me.
Solved! 4 tools
I really struggled with starting this because the problem says to start at 1 and 2, and the series starts at 0 and 1, and that's a hill I will die on :D Since adding the extra 0 and 1 wouldn't break anything (since we're summing evens), I stubbornly did that.
My solution is similar to Pilsner's except I used a Multi-Row formula tool to both start the sequence (instead of Join/Union) and then find the subsequent characters.
Sticking with Generate Rows String Coding in Alteryx for as long as possible (basically building for loops)!
An = 1*A(n-1) + 2*B(n-1)
Bn = 2*A(n-1) + 3*B(n-1)
and yes, the integer factors used (1,2,3) are indeed also Fibonacci numbers.
Anyway, we can use this in the Generate Rows Tool to immediately generate all relevant data in a single shot, calculate the corresponding Fibonacci number and sum them up to arrive at the answer with a fairly clean 3 tool workflow.
Happy Solving!
