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.
The best solution (in my view) generates the Fibonacci sequence term by term, but only keeps the most recent two terms. Whenever a new term is even, add it to the result. When a term meets or exceeds the cap, we're done.
Binet's formula implies that as \(k\) increases, the \(k\)-th Fibonacci number approaches \(\frac{\varphi^k}{\sqrt 5}\), where \(\varphi = \frac{1 + \sqrt 5}2\) (the "golden ratio"). If \(\frac{\varphi^k}{\sqrt 5} \leq n\), then \(k \leq \log_\varphi (\sqrt 5 n) = \frac{1}{\log \varphi}(\log \sqrt 5 + \log n)\). The asymptotic runtime is therefore \(O(\log n)\).
def p2(n=4000000):
res, f1, f2 = 0, 1, 1
while f2 < n:
if f2 % 2 == 0:
res += f2
f1, f2 = f2, f1 + f2
return res