How To Check If A Given Number Is a Fibonacci Number Using Python?

How To Check If A Given Number Is a Fibonacci Number Using Python?
How To Check If A Given Number Is a Fibonacci Number Using Python?

Introduction

Fibonacci series of numbers is a series of numbers formed by the addition of the preceding two numbers. The term ‘Fibonacci’ for such a sequence of numbers was coined in the 12th century by Leonardo Fibonacci, who was stumbled by the curious problem of a fictional Rabbit’s breeding process.

The problem statement requires us to check whether a given number is a Fibonacci number or not. It is one of the most fundamental questions in the interview world asked by Amazon, Snapdeal, and Adobe.

Over time the Fibonacci series in Python has marked its importance in the initial stages of selection for Software Development Engineer. The program is enough to check the logical ability and Mathematical concepts of a programmer.

Go further and try out this question on your own before moving on to the Solution.


What is a Fibonacci Number?

The problem at hand is: “Given a number N, check whether N belongs to the Fibonacci sequence or not”. In simple terms, check whether the given number is a Fibonacci number or not. The addition of the preceding two numbers forms a Fibonacci sequence, wherein the first and second number of the sequence is 0 and 1 respectively.

Let the sequence be denoted by fib, where f1, f2,………….., fn denotes the first, second, and nth terms of the Fibonacci sequence.      

f1 = 0, f2 = 1
f3 = f1 + f2 = 0 + 1 = 1
f4 = f2 + f3 = 1 + 1 = 2
f5 = f3 + f4 = 1 + 2 = 3
f6 = f4 + f5 = 2 + 3 = 5
………………………….
………………………….
………………………….
………………………….
………………………….
………………………….
 fn = fn-2 + fn-1

The pattern can thus be represented as the sequence 0, 1, 1, 2, 3, 5, …………..

Below is the output of the Fibonacci series program:

Fibonacci Series Program

The following program can be used to generate the Fibonacci series in Python.

N = int(input("Enter the number of terms : "))
 
# first two terms are f1, f2 equal to 0 and 1 respectively
f1, f2 = 0, 1
count = 0
 
# checking for invalid inputs
if(N <= 0):
    print("Invalid Input, Kindly enter number greater than 0")
 
# if only one number in the sequence
elif(N == 1):
    print("Generating Fibonacci Sequence upto ", N, ": ")
    print(f1)
 
# for all the other cases, i.e. when N > 1
else:
    print("Generating Fibonacci sequence upto ", N, ": ")
    while count < N:
        print(f1)
        fth = f1 + f2
# swapping the values for f1 and f2
        f1 = f2
        f2 = fth
        count += 1

The above program will generate the Fibonacci Series in Python. The Fibonacci series in Python can also be generated using Recursion as follows:

# Python program to display the Fibonacci sequence using Recursion
 
def fibonacci_recur(n):
   
   if n <= 1:
       return n
 
   else:
        # recursive call for (n-1) and (n-2)
       return(fibonacci_recur(n-1) + fibonacci_recur(n-2))
 
count = input("Enter number of terms: ")
 
# check if the number of terms is valid
if count <= 0:
   print("Plese enter a positive numbee")
else:
   print("Generating Fibonacci sequence upto :", count, ": ")
   for i in range(count):
       print(fibonacci_recur(i))

The time complexity will be T(n – 1) + T(n – 2) which is exponential. Alternatively, we can also use Dynamic Programming (Memoization) to generate the Fibonacci series as follows: 

blog banner 1
# Function for nth fibonacci number - Dynamic Programming
# Taking 1st two fibonacci nubers as 0 and 1
Fibonacci_Array = [0, 1]
 
def fibonacci_DP(n):
 
    # Check is n is less than 0
    if n <= 0:
        print("Incorrect input")
    # if the numbers of terms in the sequence are to be 1 or 2  
    elif n <= len(Fibonacci_Array):
        return Fibonacci_Array[n - 1]
    else:
        temp_fib = fibonacci_DP(n - 1) + fibonacci_DP(n - 2)
	  # .append() is used for adding elements to the last of
	  #  the array
        Fibonacci_Array.append(temp_fib)
        return temp_fib
 
count = int(input("Enter the number of terms"))
for i in range(1, count+1):
    print(fibonacci_DP(i))

The time complexity will be O(N), where N is the number of terms in the Fibonacci sequence.

Program to check if a given number is a Fibonacci number or not

Approach 1

To check if a given number is a Fibonacci number, a simple technique is to generate Fibonacci numbers until the generated numbers are greater than or equal to the given number, ‘N.’ In other words, generate Fibonacci series in python till the generated numbers are greater than or equal to N.

Sample Input and Output:

Example 1
Input:  Enter the number you want to check: 34
Output: Given number is Fibonacci number

Explanation: 34 is a Fibonacci number

Example 2
Input: Enter the number you want to check: 45
Output: No it’s not a Fibonacci number

Explanation: 45 is not a Fibonacci number

Program

N = int(input("Enter the number you want to check: "))
 
# variables for generating fibonacci sequence
f3 = 0
f1 = 1
f2 = 1
# 0 and 1 both are fibonacci numbers
if (N == 0 or N == 1):
    print("Given number is fibonacci number")
 
else:
    # generating the fibonacci numbers until the generated number is less than  N
    while f3 < N:
        f3 = f1 + f2
        f2 = f1
        f1 = f3
    if f3 == N:
        print("Given number is fibonacci number")
    else:
        print("No it’s not a fibonacci number")

Approach 2

An essential property about Fibonacci numbers is that a number N is Fibonacci if and only if either one of (5N^2 + 4) or (5N^2 – 4) is a perfect square.

Sample Input and Output

Example 1:
Input: 6
Output: 6 is not a Fibonacci number

Explanation: 6 do not form a part of the Fibonacci series


Example 2:
Input: 233
Output: Given number is Fibonacci number

Explanation: 233 is a part of the Fibonacci series

Program

import math
 
# A utility function that will return true 
# if the number is perfect square, else this
# will return false
def isPerfectSquare(num):
    # finding the square root of num
    s =int(math.sqrt(num))
    return s*s == num
 
def isFibonacciNumber(n):
    # return true if the number is fibonacci otherwise
    # return false
    return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4)
 
 
n = int(input("Enter the number you want to check : "))
if(isFibonacciNumber(n) == True):
    print("Given number is fibonacci number")
else:
    print(n  ," is not a fibonacci number")

Frequently Asked Questions

How do you check if a number is Fibonacci or not Python?

To check if the given number is a Fibonacci number in Python, use the following property, i.e., A number is Fibonacci if and only if 5n^2 + 4 or 5n^2 – 4 is a perfect square.
Functional implementation of the approach: 
A utility function that will return true
if the number is perfect square, else this
will return false
def isPerfectSquare(num):
# finding the square root of num
s =int(math.sqrt(num))
return s*s == num
def isFibonacciNumber(n):
# return true if the number is fibonacci otherwise
# return false
return isPerfectSquare(5nn + 4) or isPerfectSquare(5nn – 4)

Is four a Fibonacci number?

No, 4 is not a Fibonacci number.

Is zero a Fibonacci number?

Yes, 0 is a Fibonacci number.

How do you check if a number is Fibonacci or not in C?

To check if the given number is a Fibonacci number, Use the same approach as discussed above. The code in C Programming languages is.

bool isPerfectSquare(int x)
{
int s = sqrt(x);
// will return true if x is perfect square
return (ss == x); } int isFibonacci(int n) { return isPerfectSquare(5nn + 4) || isPerfectSquare(5n*n – 4);
}
int main()
{
int num;
printf(“Enter a number”);
scanf(“%d”, &num);
if(isFibonacci(num)){
printf(“%d is a fibonacci number”, num);
}
else{
printf(“%d is not a fibonacci number”, num);
}
return 0;
}

Key Takeaways

Fibonacci series is an important topic from an interview perspective in the initial stages. This blog covered an overview of basic concepts regarding it, owing to which many different sets of problems can be attempted. Feel free to explore more of the Fibonacci series, practice more questions on CodeStudio

“Curiosity is the spark behind the spark of every great idea. The future belongs to the curious”. #BeCurious

By Manvi Chaddha