Visualizing the Last Digits of Fibonacci Numbers
If you write out a sequence of Fibonacci numbers, you can see that the last digits repeat every 60 numbers. We'll use Python to visualize the data.
Join the DZone community and get the full member experience.Join For Free
if you write out a sequence of fibonacci numbers, you can see that the last digits repeat every 60 numbers.
the 61st fibonacci number is 2504730781961. the 62nd is 4052739537881. since these end in 1 and 1, the 63rd fibonacci number must end in 2, etc. and so the pattern starts over.
it’s not obvious that the cycle should have length 60, but it is fairly easy to see that there must be a cycle. there are only 10*10 possibilities for two consecutive digits. since the fibonacci numbers are determined by a two-term recurrence, and since the last digit of a sum is determined by the sum of the last digits, the sequence of last digits must repeat eventually. here “eventually” means after at most 10*10 terms.
replace “10” by any other base in the paragraph above to show that the sequence of last digits must be cyclic in any base. in base 16, for example, the period is 24. in hexadecimal notation the 25th fibonacci number is 12511 and the 26th is 1da31, so the 27th must end in 2, etc.
here’s a little python code to find the period of the last digits of fibonacci numbers working in any base b.
from sympy import fibonacci as f def period(b): for i in range(1, b*b+1): if f(i)%b == 0 and f(i+1)%b == 1: return(i)
this shows that in base 100 the period is 300. so in base 10 the last two digits repeat every 300 terms.
the period seems to vary erratically with base as shown in the graph below.
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.