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.

[Qiu]

Your guys minimum tool approach is very impressive, but I will just go with boring iterative macro. 😁

Spoiler

[BS_THE_ANALYST]

@gawa I can't wait to dissect that generate rows 😂. 

There's some amazing solutions in here so far. I love @CoG's thoughts on this too.

Thanks for sharing guys, I'm learning alot 🙏.

I went for a simple solution whilst I still can 😂. 

Spoiler

 

[BS_THE_ANALYST]

Okay, I want to say thanks to @gawa and @CoG  today. You've both taught me alot. I didn't realise quite how powerful a generate rows could be in terms of storing variables in a cheeky way!

@CoG, I decided to invert your logic and look into seeing if Even Fibonnacci numbers can generate other even Fibonnacci numbers. Which it can. Confirmed on the classic excel spreadsheet 😂🥴

Spoiler

 My Upgraded Solution (only considering even Fibonacci numbers)

Spoiler

Learning so much from everyone, thanks guys! This is what makes this community great.

[caltang]

Iterative Macro ftw!

Spoiler

[BS_THE_ANALYST]

@caltang YOOOO

That's pretty weird 🤔. Sum of odd fibonnaccis and sum of even fibonnaccis has a difference of 1 based on your screenshot. 

Interesting .. I wouldn't have expected that?!

[caltang]

So cool right? Blows my mind too.

[pilsworth-bulien-com]

Thats really interesting @caltang and @BS_THE_ANALYST , I never would have thought that either! 

Naturally, after you both pointed this out, I then went down a mini rabbit hole to see if there is this could be generalised or even proven. As @CoG pointed out, the sequence follows and odd, odd, even pattern. Also, thinking about the main rule (each term is the sum of the previous 2 terms) it does then start to make sence. 

If I write out the first 12 terms they are, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. But I could equally write the sequence formatted as follows (you have to read it left to right, like a book):

COLUMN 1	COLUMN 2	COLUMN 3
0
1	1	2
3	5	8
13	21	34
55	89	144

When written like this its easy to see that all the even numbers appear in the Right column, and the other columns are odd (we wont talk about 0). 

We can also see that Column 1 + Column 2  = Column 3, (We know this is true anyway from the fibonacci sequence definition).

The sum of the even numbers is Sum(Column 3).

The sum of the odd numbers is Sum(Column 1 + Column 2) BUT as we just saw from before, Column 1 + Column 2  = Column 3, therefore by doing a simple substitution:
The sum of the odd numbers can also be writen as Sum(Column 1 + Column 2) = Sum(Column 3) which is the sum of the even numbers!

I havent looked yet (I will do in a moment), but I assume @caltang started with 1,2 as the first two terms of the sequence, as the question instructs. 

I agree with @Carolyn , the sequence should start 0,1,1,2 not 1,2 (but thats the questions fualt). However, the missing "1" will explain why in @caltang's solution, the odd numbers sum to one less than the even numbers. 

Finally, this will only work if you finish on an even number (so that if you format the sequence in a table like me, you have a compleate row). 

This sum rule may have been more obvious to others but I certainly didnt see it at first. More proof of how cool the Fibonacci sequence really is!

[Carolyn]

Wow... I never would've thought of looking for a pattern just to generate the evens but that's genius and so freaking cool

[mmontgomery]

Nothing fancy, just a macro i built a few years ago

Spoiler

[pilsworth-bulien-com]

Pretty much the same as @BS_THE_ANALYST's one tool solution, but after seeing that generare rown technique and the idea of calculating the even terms only from @gawa and @CoG, I had to give it a go myself. 
 

Spoiler

Each row is structured in 3 sections, delimited by the underscores, and should read as follows.

PreviousEvenTerm_CurrentEvenTerm_RunningTotal

The regex looks pretty horrid but it is effectivly doing three things.

 

1) It implements the formula to find the next even term: 4 * PreviousEvenNumber + Pervious(PreviousEvenNumber). 

2) Addes the latest term to the running total

3) Formats the record in the 3 section string (PreviousEvenTerm_CurrentEvenTerm_RunningTotal)

 Learnt a lot from these solutions! Ill definitly be looking to use that generate rows trick again in the future!