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

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

You can also try this code with Online Python Compiler

Run Code

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))

You can also try this code with Online Python Compiler

Run Code

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: 

# 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))

You can also try this code with Online Python Compiler

Run Code

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

Also see, Swapcase in Python

Approach 1

To check if a given number is 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")

You can compile it with online python compiler.

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")

You can also try this code with Online Python Compiler

Run Code

 Read about - Strong number in c and Fibonacci Series in JavaScript

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;
}

Conclusion

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

Also read: fibonacci series in c

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