5 Best Ways to Check if a Number is a Fibonacci Term in Python

💡 Problem Formulation: You need to determine if a number provided by the user is part of the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Given an input number, the output should clearly indicate whether the number belongs to the Fibonacci series or not.

Method 1: Generating Fibonacci Sequence Until The Number

This method involves generating Fibonacci numbers until the sequence has reached or passed the given number. It’s straightforward and derives from how the Fibonacci sequence is defined. If the number is found in the sequence generated, then it’s a term of Fibonacci.

Here’s an example:

def is_fibonacci(num):
    a, b = 0, 1
    while a < num:
        a, b = b, a + b
    return a == num

print(is_fibonacci(34))

Output: True

This code snippet defines a function is_fibonacci() that will generate Fibonacci terms starting with 0 and 1 until it either hits or surpasses the given number. If the generated number matches the input, the function returns True, indicating that the input number is indeed part of the Fibonacci sequence.

Method 2: Using a Mathematical Property

A number is a Fibonacci term if and only if one of (5*n^2 + 4) or (5*n^2 – 4) is a perfect square. This method checks the given number using this property, which is more efficient as it does not require generating the sequence.

Here’s an example:

import math

def is_fibonacci(num):
    x = 5 * num * num
    return math.isqrt(x+4)**2 == x+4 or math.isqrt(x-4)**2 == x-4

print(is_fibonacci(34))

Output: True

This code snippet defines the is_fibonacci() function that checks the mathematical properties involving the squares. It uses math.isqrt() to check if the result is an integer. If either of the checks passes, the function returns True.

Method 3: Using Binet’s Formula

Binet’s formula provides a direct way of computing a Fibonacci number without iteration or recursion. You can check if the number is a Fibonacci term by applying the inverse of Binet’s formula and checking if the result is an integer.

Here’s an example:

import math

def is_fibonacci(num):
    phi = (1 + math.sqrt(5)) / 2
    index = math.log(num * math.sqrt(5) + 0.5) / math.log(phi)
    return round(index) == index

print(is_fibonacci(34))

Output: True

The is_fibonacci() function defined here computes the index of the number in the Fibonacci sequence using Binet’s formula. It then checks if the index is an integer, as non-integer indices would not correspond to actual numbers in the Fibonacci sequence.

Method 4: Recursive Sequence Generation

For smaller numbers, a recursive approach can be utilized to generate Fibonacci terms until the number is found or the terms generated surpass it. However, this method is not suitable for large input numbers due to stack limitations.

Here’s an example:

def is_fibonacci(num, a=0, b=1):
    if a == num:
        return True
    if a > num:
        return False
    return is_fibonacci(num, b, a+b)

print(is_fibonacci(34))

Output: True

This recursive function is_fibonacci() keeps computing Fibonacci terms with a base case that stops the recursion when the generated term equals or exceeds the input number. It will return True if the number is part of the sequence.

Bonus One-Liner Method 5: List Comprehension with Short-Circuit Evaluation

This one-liner method generates Fibonacci numbers on the fly and checks if the given number is in the set. It’s a concise approach but not efficient for large numbers, as the whole sequence up to the number is generated.

Here’s an example:

is_fibonacci = lambda num: num in (lambda x: (y := 0, z := 1, None) or [None for _ in range(x) if (y := z + (z := y)) or True][-2])(num)

print(is_fibonacci(34))

Output: True

Using a lambda function along with list comprehension, this one-liner checks for the existence of the input number within the dynamically generated Fibonacci sequence. This is a clever use of the walrus operator to update sequence values within the list comprehension.

Summary/Discussion

• Method 1: Generating Fibonacci Sequence Until The Number. Strengths: Intuitive, simple to understand. Weaknesses: Inefficient for large numbers.
• Method 2: Using a Mathematical Property. Strengths: Efficient, no need for sequence generation. Weaknesses: Requires knowledge of a specific numerical property.
• Method 3: Using Binet’s Formula. Strengths: Direct determination without iteration, efficient. Weaknesses: Precision can be an issue with extremely large numbers.
• Method 4: Recursive Sequence Generation. Strengths: Conceptually simple. Weaknesses: Can cause stack overflow for large numbers, not practical for large inputs.
• Bonus Method 5: List Comprehension with Short-Circuit Evaluation. Strengths: Compact one-liner. Weaknesses: Potentially very inefficient, unclear and cryptic.