Loading ...Problem Description
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, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Analysis
The approximate ratio between two consecutive terms in the Fibonacci sequence is the golden ratio (phi, or φ ≈ 1.618034). It can also be demonstrated that every 3rd term of the sequence is even. By combining this knowledge we can calculate the series of even Fibonacci numbers by multiplying the previous even term in the series by the cube of the golden ratio.
Solution
Runs < 1 second in Python.
limit = 4000000 phi_cubed = ((1+5**.5)/2)**3 #golden ratio cubed f = 2 sum = 0 while f < limit: sum += f f = round(f*phi_cubed) print "Answewr to PE2 - ",int(sum)
Comments
For a limit of 4,000,000 the loop iterates 10 times.
Your method is neat, but it’s not particularly efficient; your use of floating points and rounding operations results in your code taking TWICE as long as a more primitive algorithm involving going through each Fibonacci number and merely adding up the even ones.
Thanks for the comment Robert. I never thought of that! I will post some timings for this limit and larger ones to see if this technique is worth it.