Iteration for Project Euler
Last time we talked about using recursion to compute Fibonacci numbers. We ran into some problems involving time complexity but were able improve our technique using memoization. As it turn out, though, we're still bound to run into memory problems using recursion. Fortunately, any recursive algorithm can be recast as an iterative algorithm that is typically more efficient. We'll see how to do that in this lab.
As usual, we'll be motivated by Project Euler. Here's the $25^{\text{th}}$ problem:
Project Euler question 25
The Fibonacci sequence is defined by the recurrence relation: $$F_n = F_{n-1} + F_{n-2}, \text{ where } F_1=F_2=1.$$ The first 12 terms will be: $$ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} F_1 & F_2 & F_3 & F_4 & F_5 & F_6 & F_7 & F_8 & F_9 & F_{10} & F_{11} & F_{12} \\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 \end{array}. $$ Note that the $12^{\text{th}}$ term, $F_{12}$, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
Recursive recap
Our memoized, recursive Fibonacci function from last week looked like so:
Unfortunately, if we try to compute the $1000^{\text{th}}$ Fibonacci number, we run into the dreaded maximum recursion depth exceeded error. As it turns out, we need to compute $F_n$ for $n$ considerably larger than $1000$, so we'll need another approach.
Iteration
Here's a purely iterative approach to computing Fibonacci numbers:
Sweet!
Solving PE 25
Now, we'll solve the $25^{\text{th}}$ Project Euler problem. I suppose the simplest thing to do would be to check the integers in succession, quitting when we find the first one that has more than 1000 digits. That will work here but, if we were interested in significantly more digits (100000 or 1000000), then it could take ridiculously long. A better approach would be to first find a bracketing interval (one that contains the solution) and to then zoom in on the interval using bisection.
So, I guess the answer oughtta be 4782. You can always check.
Your problem
Recall the sequence defined by the recurrence
Find the first index of the number with at least digits.
To submit your solution, you should respond to my email with subject line "Problems Lab 3 #1". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.