Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be:
$$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
To do this, we will first have to generate the Fibonacci sequence until we reach a number that exceeds four million, remembering to only sum the even-valued terms.
Recall that the Fibonacci sequence starts with 1 and 2, and each subsequent number is the sum of the previous two numbers.
Let’s start:
1. 1 + 2 = 3
2. 2 + 3 = 5
3. 3 + 5 = 8
4. 5 + 8 = 13
5. 8 + 13 = 21
6. 13 + 21 = 34
7. 21 + 34 = 55
8. 34 + 55 = 89
9. 55 + 89 = 144
This can go on and on, remembering that we will stop after we pass 4,000,000. In each of these steps, we are adding the last two numbers in the sequence to get the next number.
To make this simpler, we can keep track of the very last number (which we will call ‘b’) and the second to the last number (which we will call ‘a’).
During each step, ‘a’ will take the value of ‘b’, while ‘b’ will take the value of ‘a+b’. We keep on doing this until ‘b’ exceeds four million
Among these numbers, the even numbers are 2, 8, 34, and so on. Therefore, their sum will be the sum of even-valued terms.
Besides, I’ll explain a bit dynamic programming, which can be used to generate Fibonacci series.
Here, we’re starting from the bottom and building our solution up to the point where we get the answer.
We can initiate a while loop, where we’re generating next terms by adding previous 2 terms and continue this loop until the term exceeds 4 million.
While generating these terms, we’ll add the terms which are even to our result.
Here’s an example of what the pseudocode might look like:
“`
a:=1, b:=2, result:=2, // start with 1 and 2, with the result as 2 since we need to include this in our sum
while b <= 4,000,000 do
temp:=b, // store the value of b before we change it
b:=a+b, // get the next term in the sequence
a:=temp, // a should now have the original value of b
if b is even then
result:=result+b // update the sum if the number is even
endif
end do
print result // This gives the sum of the even-valued terms
“`
To optimize this, you can note that every third term in the Fibonacci sequence is even.
You can update your code to reflect this and get rid of the if-check in the while loop completely.
Here’s the pseudo code for generating even terms only:
“`
a:=1, b:=1, c:=a+b, result:=0, // starting with 1, 1 and 2
while c <= 4,000,000 do
result := result + c, // c always refers to the even term
a:=b+c, // next term for a
b:=a+c, // next term for b
c:=a+b, // next term for c
end do
print result // This gives the sum of the even-valued terms
“`
This question is actually Project Euler Problem 2.