Project Euler: Fibonacci Numbers and Problem 25

The Fibonacci numbers are a sequence of integers defined by the recurrence relation

\displaystyle F_{n+2}=F_{n+1}+F_{n},\text{ where }F_{0}=0,F_{1}=1

Project Euler Problem 25 asks us to find the first Fibonacci number to contain at least 1000 digits. The exact problem statement is reproduced below.

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

The brute-force way to solve this problem is to compute the n^{th} Fibonacci number and check whether it contains 1000 digits. Note that an integer with 1000 digits requires at least \lfloor{\log_{2}10^{999}+1}\rfloor=3319 bits of memory. We implement this algorithm with the following Python code:

#Import the math and time modules
import math, time
#The first two elements of the Fibonacci sequence are 0 and 1.
#We want to keep track of the index of the term with n.
F0 = 0; F1 = 1; n = 1
#The smallest 1000-digit number has logarithm in base 10 equal to 999 (i.e. 10**999).
#We want to see how long this algorithm will take.
start_time = time.time()
while math.log(F1,10) < 999:
    #Update the index
    n += 1
    #Compute the n^th Fibonacci number
    F2 = F0+F1
    F0 = F1
    F1 = F2
elapsed_time = time.time() - start_time
print n, elapsed_time

The algorithm computes Fibonacci numbers and keeps track of their index until the first 1000-digit Fibonacci number has been computed, upon which the while loop terminates. It then spits out the index of the first 1000-digit Fibonacci number, which is 4782. Given that the code only took .029 seconds to execute on my computer, it got the job done in a reasonable amount of time. However, it’s not exactly a scalable solution.

The smart way to solve this problem is to use…more math! We can solve this linear recurrence equation with a generating function F(z)=\sum_{n=0}^{\infty}F_{n}z^{n}. Technically, we haven’t shown that that the power series giving F(z) has positive radius of convergence. So the following is formal manipulation:

\begin{array}{lcl}\displaystyle F(z)=F_{0}+F_{1}z+\sum_{n=2}^{\infty}F_{n}z^{n}&=&\displaystyle F_{0}+F_{1}z+z^{2}\sum_{n=0}^{\infty}F_{n+2}z^{n}\\[1.5 em]&=&\displaystyle F_{0}+F_{1}z+z^{2}\sum_{n=0}^{\infty}\left(F_{n}+F_{n+1}\right)z^{n}\\[1.5 em]&=&\displaystyle z+z^{2}F(z)+z^{2}\sum_{n=0}^{\infty}F_{n+1}z^{n}\\[1.5 em]&=&\displaystyle z+z^{2}F(z)+zF(z)\end{array}

Rearranging, we see that F(z) satisfies the equality

\displaystyle F(z)=\dfrac{z}{1-z^{2}-z}

Observe that the roots of the quadratic polynomial 1-z-z^{2} are

\displaystyle-\dfrac{1+\sqrt{5}}{2}=-\varphi\text{ and }-\dfrac{1-\sqrt{5}}{2}=-\psi

We can rewrite the expression for F(z) as

\begin{array}{lcl}\displaystyle F(z)=-\dfrac{z}{(z+\varphi)(z+\psi)}&=&\displaystyle-\dfrac{1}{\psi-\varphi}\left[\dfrac{z}{z+\varphi}-\dfrac{z}{z+\psi}\right]\\[2 em]&=&\displaystyle-\dfrac{z}{\psi-\varphi}\left[\varphi^{-1}\sum_{n=0}^{\infty}(-1)^{n}\varphi^{-n}z^{n}-z\psi^{-1}\sum_{n=0}^{\infty}(-1)^{n}\psi^{-n}z^{n}\right]\\[2 em]&=&\displaystyle-\dfrac{z}{\psi-\varphi}\sum_{n=0}^{\infty}(-1)^{n}\dfrac{\psi^{n+1}-\varphi^{n+1}}{\psi^{n+1}\varphi^{n+1}}z^{n}\\[2 em]&=&\displaystyle-\dfrac{z}{\psi-\varphi}\sum_{n=0}^{\infty}(-1)^{n}\dfrac{\psi^{n+1}-\varphi^{n+1}}{(-1)^{n+1}}z^{n}\\[2 em]&=&\displaystyle\sum_{n=0}^{\infty}\dfrac{\psi^{n+1}-\varphi^{n+1}}{\psi-\varphi}z^{n+1}\end{array}

Multiplying by 1 and comparing coefficients, we see that

\displaystyle F_{n}=\dfrac{\varphi^{n}-\psi^{n}}{\varphi-\psi}=\dfrac{\varphi^{n}-\psi^{n}}{\sqrt{5}},\indent\forall n\geq1

  A neat consequence of this closed-form expression for F_{n} is that the limit of the ratio of consecutive Fibonacci numbers is the golden ratio \varphi. Indeed,

\displaystyle\lim_{n\rightarrow\infty}\dfrac{F_{n+1}}{F_{n}}=\dfrac{5^{-\frac{1}{2}}\left(\varphi^{n+1}-\psi^{n+1}\right)}{5^{-\frac{1}{2}}\left(\varphi^{n}-\psi^{n}\right)}=\dfrac{\varphi-\varphi^{-n}\psi^{n+1}}{1-\varphi^{-n}\psi^{n}}

Since \left|\psi\right|<1, the quantities \psi^{n+1} and \psi^{n} tend to 0 as n\rightarrow\infty. Since \left|\varphi\right|>1, the quantity \varphi^{-n} tends to 0 as n\rightarrow\infty. Applying the continuity of arithmetic operations, we conclude that

\displaystyle\lim_{n\rightarrow\infty}\dfrac{F_{n+1}}{F_{n}}=\dfrac{\varphi-\displaystyle\lim_{n\rightarrow\infty}\varphi^{-n}\psi^{n+1}}{1-\displaystyle\lim_{n\rightarrow\infty}\varphi^{-n}\psi^{n}}=\dfrac{\varphi-0}{1-0}=\varphi

  The closed-form expression for F_{n} also allows us to find the index of the Fibonnaci number with a given number of digits. To see this, observe that \left|\psi\right|<1 and \sqrt{5}>2, hence

\displaystyle\dfrac{\left|\psi\right|^{n}}{\sqrt{5}}<\dfrac{1}{2}

Since F_{n} is an integer and

\displaystyle\left|F_{n}-\dfrac{\varphi^{n}}{\sqrt{5}}\right|=\left|\left(\dfrac{\varphi^{n}-\psi^{n}}{\sqrt{5}}\right)-\dfrac{\varphi^{n}}{\sqrt{5}}\right|=\dfrac{\left|\psi\right|^{n}}{\sqrt{5}}<\dfrac{1}{2}

we conclude that the n^{th} Fibonnaci number is the integer closest to \frac{\varphi^{n}}{\sqrt{5}}.

How can we use this result to find the index of the smallest 1000-digit Fibonacci number F? Well, if we can find the minimal n such that

\displaystyle\dfrac{\varphi^{n}}{\sqrt{5}}>10^{999},

then will be very close to n(F)\in\left\{n,n-1\right\}. Remember that, without doing more work, we don’t know that F=10^{999}. Taking the logarithm of both sides in base \varphi, we see that n must satisfy the inequality

\displaystyle n>\log_{\varphi}\left(\sqrt{5}\cdot10^{999}\right)

Before you go plugging the right-hand side into the Python interpreter, 10^{999} is too large of an integer for Python to convert it to floating-point, so we need to be smart about this computation. Using the logarithm change-of-base formula, we see that

\begin{array}{lcl}\displaystyle\log_{\varphi}\left(\sqrt{5}\cdot 10^{999}\right)=\left(\log_{\varphi}10\right)\left(\log_{10}\sqrt{5}10^{999}\right)&=&\displaystyle\left(\log_{\varphi}10\right)\left(\log_{10}\sqrt{5}+999\right)\\&\approx&\displaystyle4781.859\end{array}

Since \varphi^{.859}>1.5, we see that \frac{\varphi^{4781}}{\sqrt{5}}+\frac{1}{2}<10^{999}, and therefore 4782 is the index of the desired of the desired Fibonacci number.

Advertisements
This entry was posted in Problem Solving, Python and tagged , , , . Bookmark the permalink.

6 Responses to Project Euler: Fibonacci Numbers and Problem 25

  1. Abishek says:

    sort of brute force scalable solution. Just have an array of 1000 digits and pretend it is the number. Individually, add the numbers and keep track of the carry. When the 1000th digit is not 0, the first time that happens, stop the counter. I get 4782 with this code.

    int main() {
    int i,sum,carry,counter;
    counter =2;// starting at 2 because intialising a1 and a2 to 1 which means we are counting the third fibo number
    int a1[1000],a2[1000],a3[1000];
    for( i =0;i<1000;i++)
    { a1[i]=0;
    a2[i]=0;
    a3[i]=0;
    }

    a1[0]=1;
    a2[0]=1;

    while(1) {

    carry = 0;
    for( i =0;i<1000;i++)
    { sum = carry + a1[i]+ a2[i];
    a3[i] = sum % 10;
    carry = sum /10;
    }

    for(i =0;i0)
    break;
    }

    printf(“counter is %d”,counter);
    }

  2. Abishek says:

    code got cut off for some reason.
    int i,sum,carry,counter;
    counter =2;// starting at 2 because intialising a1 and a2 to 1 which means we are counting the third fibo number
    int a1[1000],a2[1000],a3[1000];
    for( i =0;i<1000;i++)
    { a1[i]=0;
    a2[i]=0;
    a3[i]=0;
    }

    a1[0]=1;
    a2[0]=1;

    while(1) {

    carry = 0;
    for( i =0;i<1000;i++)
    { sum = carry + a1[i]+ a2[i];
    a3[i] = sum % 10;
    carry = sum /10;
    }

    for(i =0;i0)
    break;
    }

    printf(“counter is %d”,counter);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s