The 1000th Fibonacci NumberDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/