Recursion for Project Euler
Today, we continue our excursion into programming motivated by Project Euler. Here's the second problem:
Project Euler question 2
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, \ldots$$ By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
This particular problem gives us a nice opportunity to talk about recursion and iteration. Generally, the first is quite elegant but the second is more efficient.
The Fibonacci numbers
The Fibonacci numbers have a lovely recursive defintion: $$ F_n = \begin{cases} n & \text{if } n=0 \text{ or } n=1 \\ F_{n-1}+F_{n-2} & \text{if } n>1. \end{cases} $$
Here's some naive code that translates that recursion directly to Python.
Unfortunately, this code runs sooo slow - even a number as small as 100 is beyond reach. To see why, let's implement a counter that keeps track of how many times the function calls itself.
Can you see why this is happening? To help, try running the code with fibr(n) for several small values of n.
There is a standard technique, called memoization, that gets around this issue by storing values that have already been computed. We can implement this like so:
To see what happened, try adding memoize.cache inside the print function.
Project Euler Solution
With that stuff in hand, we can now determine a solution to the Project Euler question.
Problem 1
Let the sequence be defined by the recurrenceFind the sum of all the numbers less than that are divisble by .
To submit your solution, you should respond to my email with subject line "Problems Lab 2 #1". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.
Closed form
Here's an amazing closed form expression for the $n^{\text{th}}$ Fibonacci number: $$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, $$ where $\phi = (1+\sqrt{5})/2$ is the Golden Ratio and $\psi = -1/\phi = (1-\sqrt{5})/2$.
One way to see why this works is as follows. The constants $\phi$ and $\psi$ are exactly the roots of $x^2-x-1$. Solving for $x^2$ and multiplying by $x^n$, we see that any root of that quadratic satisfies, $$x^{n+2} = x^{n+1} + x^n.$$ That is, the sequences $\phi^n$ and $\psi^n$ both satisfy the Fibonacci recurrence. As a result, so does any linear combination $a\phi^n + b\psi^n$. If we can just choose $a$ and $b$ so that $$ \begin{align} a \phi^0 + b \psi^0 &= 0 \\ a \phi^1 + b \psi^1 &= 1 \\ \end{align}, $$ then we must also have $a \phi^n + b \psi^n = F_n$ for all $n$!
We can automate the process of finding $a$ and $b$ using Sage and then checking that it works as follows:
Problem 2
Implement a closed form expression for the numbers and compute the first ten of them.
To submit your solution, you should respond to my email with subject line "Problems Lab 2 #2". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.