Fibonacci series and its properties Pisano Period in Python

By Vishal Kumar

Fibonacci number and it,s naive algorithm together with faster algorithm using memoization and iteration. And also it,s properties mainly Pisano period and it,s implementation in Python.

Fibonacci series consist of elements in which it,s current term are sum of previous two consective terms.

F[n]=F[n-1]+F[n-2]

series will look alike: 0,1,1,2,3,5,8,13,21,34,55,89,144...............

One can write the naive code of Fibonacci series by just looking at defination:

def fibonacci(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        value=fibonacci(n-1)+fibonacci(n-2)
        return value

But above naive algorithgm runs very slow as in recurssion at each step for higher fibonacci number it has to recall the same recurssion many times. So to avoid this ,we can use memoization technique in which we store the value of recurssion by creating dictionary and every another time if same recurssion got called we can use the value from stored recurssion ,hence making the program to run much faster.

Faster algorithm by using memoization:

fib_cache={}
def feb(n):
    if n in fib_cache:
        return fib_cache[n]
    if n==1:
        return 1
    elif n==2:

        return 1
    else:
        value=feb(n-1)+feb(n-2)
    fib_cache[n]=value
    return value

Another way to run the faster algorithm of fibonacci series are using iteration. In Itertaion ,we make trade-off between space and time. For faster algorithm we need to put more space. In this method, intially only we create the list of n size and  thereafter by using for loop me calculate present term in each loop by adding previous two term.

Faster algorithm by using Iteration:

def fiblist(n):
    if n<=1:
        return n
    else:
        fib=[None]*(n+1)
        fib[0]=0
        fib[1]=1
        for i in range(2,n+1):
            fib[i]=fib[i-1]+fib[i-2]
        return fib[n]

Pisano Period

It is the special properties of fibonacci number in which after dividing elements of fibonacci series by another number gives whatever remainder it folow periodic relation among themselves and repeat themselves after certain period. Pattern of remainder is that next term of remainder is equal to "sum of previous two term divided by that number". Pisano period of any number start with 0 and 1 and it,s period will be untill that 0 and 1 again encounter in that remainder series. You will get better idea after looking it,s implementation code:

def pisano_period(m):
    assert 0 <= m <= 10 ** 3
    periodlist=[0,1,1]
    prev,curr=1,1%m
    while prev!=0 or curr!=1:
        prev,curr=curr,(prev+curr)%m
        periodlist.append(curr)
    period=len(periodlist)-2
    return period

we can use this pisano period to solve many problems related with fibonacciu number that also of huge number. We can find the sum of last digit of elemet of fibonacci series upto 10**15 number . Similarly we can find out the sum of square of last digit of element of fibonacci series. Many more problems related with remainder and last digit of fibonacci number can be solved by pisano period. Some of them are as follows:

Sum of unit digit of fibonacci numbers

def sum_of_unit_digit_of_fibonacci_numbers(n):
    assert 0 <= n <= 10 ** 18
    periodlist=[0,1,1]
    prev,curr=1,1%10
    while prev!=0 or curr!=1:
        prev,curr=curr,(prev+curr)%10
        periodlist.append(curr)
    period=len(periodlist)-2
    periodsum=sum(periodlist)-1
    p=(n//period)*periodsum
    q=sum(periodlist[:(n%period)+1])
    return (p+q)

Atlast , I want to conclude that by using correct faster algorithm and it,s properties we can find out the fibonacci number of very large number also.