Problem:
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, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
The first requirement is to implement the Fibonacci function, here is a naive implementation:
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)But in this implementation, time is exponential: T(n) = T(n-1) + T(n-2)1.
Below is a memoized implementation (for an introduction, I encourage you to watch this course on that subject: 19. DynamicProgramming I: Fibonacci, Shortest Paths).
In short, we’re keeping a trace of each calculated values, so that we can reuse them along. This method reduce considerably the time complexity.
memo = {}
def fib(n):
if n in memo:
return memo[n]
else:
if n <= 2: f = 1
else:
f = fib(n-1) + fib(n-2)
memo[n] = f
return fHere is the final algorithm, the other parts are just a matter of list filtering.
memo = {}
def fib(n):
if n in memo:
return memo[n]
else:
if n <= 2: f = 1
else:
f = fib(n-1) + fib(n-2)
memo[n] = f
return f
# Here I found the right value to be 35, but only by trial and error,
# an update would be to stop automatically at the right key
fib(35)
# We get the list of values under 4M
under_stop = [x for x in list(memo.values()) if x < 4000000]
# Then a list of even numbers
even_list = [x for x in under_stop if x % 2 == 0]
# Finally the sum
print(sum(even_list))Footnotes
If you don’t believe this is bad, try doing fib(50) 🙂↩︎