Associated Topics || Dr. Math Home || Search Dr. Math

### The 1000th Fibonacci Number

```
Date: 09/25/98 at 11:27:39
From: Francois Compain
Subject: Fibonacci sequence

Hi,

I was asked by my teacher to find the 1000th number in the Fibonacci
sequence. I was able to make a program for my calculator, but I
couldn't go beyond the 450th number. Could you help me find the 1000th?

Thanks.
```

```
Date: 09/25/98 at 13:42:42
From: Doctor Rob
Subject: Re: Fibonacci sequence

The number you seek has 209 decimal digits. Your calculator will have
to be able to deal with that, or else you will have to do this on
paper. Do you need all the digits, or will an approximation do?  For
example:

F(450) = 495396701187506647316252492523160404772779187134606\
1001150551747313593851366517214899257280600

or approximately 4.953967011875 * 10^93. Will the latter do?

If an approximation will work, try this to find the nth Fibonacci
number F(n) (where F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, and so on).
Compute phi = (1+sqrt[5])/2, and take its logarithm (base 10).
Multiply that by n, and subtract half the logarithm (base 10) of 5.
This will be the logarithm (base 10) of your answer. The integer part
will tell you the exponent of 10 in the approximation, and raising 10
to the fractional part power will tell you the first several digits of
the first factor of the approximation.

Example:  n = 12
phi = 1.6180...
log_10(phi) = 0.2090...
12*log_10(phi) = 2.5079...
log_10(5)/2 = 0.3495...

The difference of the last two numbers is 2.1584..., and
10^0.1584... = 1.44001..., so the approximation is 1.44001*10^2.
Of course F(12) = 144, so this is an excellent approximation.

This works because phi^n/sqrt(5), when rounded to the nearest integer,
gives F(n) exactly, and the approximation gets better the bigger n is.

If you need all the digits, you can proceed as follows.

Start with two sequences F(n) above, and L(n), defined by L(0) = 2,
L(1) = 1, and L(n) = L(n-1) + L(n-2) for every n >= 2. The L sequence
is called the Lucas Sequence, and goes 2, 1, 3, 4, 7, 11, 18, 29, 47,
76, 123, and so on.  Now there are the following identities between
these numbers:

1.  F(2*n) = F(n)*L(n)
2.  L(2*n) = L(n)^2 - 2*(-1)^n
3.  F(n+1) = [L(n)+F(n)]/2
4.  L(n+1) = [L(n)+5*F(n)]/2

which are true for all positive values of n. These allow you to
compute F(1000) if you know F(500) and L(500), by using 1 above with
n = 500. These two you can find from F(250) and L(250), by using 1 and
2 above with n = 250. These two you can find from F(125) and L(125),
by using 1 and 2 above with n = 125. These two you can find from
F(124) and L(124), by using 3 and 4 above with n = 124. These two you
can find from F(62) and L(62), by using 1 and 2 above with n = 62.
These two you can find from F(31) and L(31), by using 1 and 2 above
with n = 31. These two you can find from F(30) and L(30), by using 3
and 4 above with n = 30. These two you can find from F(15) and L(15),
by using 1 and 2 above with n = 15. These two you can find from F(14)
and L(14), by using 3 and 4 above with n = 14. These two you can find
from F(7) and L(7), by using 1 and 2 above with n = 7. These two you
can find from F(6) and L(6), by using 3 and 4 above with n = 6. These
two you can find from F(3) and L(3), by using 1 and 2 above with
n = 3.

Now you know that F(3) = 2 and L(3) = 4, so you can work back up the
chain in the last paragraph to find F(6) = 8 and L(6) = 18, F(7) = 13
and L(7) = 29, and so on until you find F(1000). Most of the work
comes at the end, when you have to multiply together F(500) and
L(500), two numbers with more than 100 decimal digits each.

In principal, 1 through 4 above will allow you to compute F(n) and
L(n) for any positive integer n, no matter how large, with only a
relatively few arithmetic operations.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/