Python Fibonacci

In this lesson we will analyze some algorithmsin Python to check if a number belongs to the Fibonacci sequence.

In the previous lesson we studied how to print a Fibonacci sequence of variable length, each time decided by the user.

We have both an iterative and a recursive solution, using functions as well.

In this lesson instead ask the user to enter an integer and the program in Python will be able to tell if it is a Fibonacci number or not.

We will develop different solutions and analyze them.

Python Fibonacci – check if a number is Fibonacci

We study a first approach to a possible solution to the proposed problem.

The first thing that comes to mind, without knowing any rules, is to generate the Fibonacci numbers up to the input entered by the user and check if this number is contained in it.

We develop the solution using an iterative solution that will stop when the condition is satisfied, in our case when the entered number is found or numbers not greater than it are generated.

We create a sentinel variable, which we will call found for example, and set it to False. After that, this variable will change its value, becoming True only if the value is included in the sequence.

Here is a possible solution:

def check_fib(num):
    found = False
    a = 1
    b = 1
    c = a + b
    print(a,  end=' ')
    print(b,  end=' ')
    while(c <= num):
        print(c, end=' ')
        a = b
        b = c
        c = a + b        
        if(c == num):
            found = True
    if(found):
        print('Found')
    else:
        print('Not Found')
        
n = int(input('Insert a number: ' ))
check_fib(n)

Python Fibonacci - check if a number is Fibonacci - second solution

In this second solution we apply the well-known mathematical rules instead.

In particular, it is said that N is a Fibonacci number if and only if 5 N ^ 2 + 4 or 5 N ^ 2 - 4 is a square number.

We therefore develop an algorithm that satisfies these conditions by importing the math module in order to be able to use the square root (sqrt) function. If the square root is an integer then it means that it is a square number and therefore belongs to the sequence, otherwise it does not belong to it.

def check_fib(n):
    import math
    a = (5 * (n**2)) + 4
    b = (5 * (n**2)) - 4
    return (math.sqrt(a)).is_integer() or (math.sqrt(b)).is_integer()

n = int(input('Insert a number: ' ))
result = check_fib(n)
if (result):
    print('The number is Fibonacci')
else:
    print('The number is not Fibonacci')

Conclusion

In this lesson we learned how to check, in Python, if a number belongs to the Fibonacci sequence or not. In the next few lessons we will talk about lists in Python.

Some useful links

Python lambda function

Use Python dictionaries

Python readline()

Python max()

Break Python

Insertion Sort

Merge Sort