Euleryx Project 2 - Even Fibonacci Numbers

[pilsworth-bulien-com]

Euleryx Problem 2 -  Even Fibonacci Numbers

 
Here's my full workflow and Answer:

Spoiler

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: 

1. 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. 
   
   
   

    

   
    
2. 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)
   
   
   

    

   
   
   
3. Now let's implement the term-to-term rule, using a multi-row formula. (Don’t forget to set the Num rows value = 2). 
    

    

4. Filter to the even values under 4,000,000 and sum them.
    
5. 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.

[Hub119]

Fun times with formulas in Generate Rows tools...

Spoiler