#2 - Even Fibonaci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 20 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terrms.
We can go through the Fibonacci numbers, generating and checking them as we go.
# file: "problem002.py"
a = 1
b = 1
s = 0
while b <= 4000000:
if b % 2 == 0:
s += b
temp = a + b
a = b
b = temp
print(s)
Running results in the following output:
4613732
0.00011090000000002487 seconds.
Bonus
However, we can also solve this analytically. If we assume $F_1=F_2=1$, then it turns out every 3rd Fibonacci number is even. This is due to:
- The sequence starts with 2 odd numbers
- An odd plus an odd gives an even
- An even plus odd gives an odd. Thus, we need to add every 3rd Fibonacci number. Recall that there is also a closed-form formula utilizing the golden ratio:
We need to find the index of the largest Fibonacci number less than 4 million. From the Wikipedia article, the formula to find the closest index (rounded down) of a Fibonacci number $F$ is \[n(F)=\lfloor \log_\Phi\left(F\sqrt{5}+\frac{1}{2}\right)\rfloor \\ n(4000000)=33\]
Next, recall that the sum of a finite geometric series is \[a_1\frac{1-r^n}{1-r}\]
where,
- $a_1$ is the first term
- $r$ is the common ratio
- $n$ is the number of terms in the sequence.
Now we can write and solve our summation like so: \[\begin{aligned} S &= \sum_{k=1}^{11}F_{3k} \\ &= \sum_{k=1}^{11}\frac{\Phi^{3k} - (1-\Phi)^{3k}}{\sqrt{5}} \\ &= \frac{1}{\sqrt{5}}\left(\sum_{k=1}^{11}\Phi^{3k} - \sum_{k=1}^{11}(1-\Phi)^{3k}\right) \\ &= \frac{1}{\sqrt{5}}\left(\Phi^3\frac{1-(\Phi^3)^{11}}{1-\Phi^3} - (1-\Phi)^3\frac{1-((1-\Phi)^3)^{11}}{1-(1-\Phi)^3}\right) \\ &= \boxed{4613732} \end{aligned}\]
