Checking for Fibonacci Numbers in Python
Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence begins as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. To determine if a given number is a Fibonacci number, one effective method is based on a mathematical property: A number \( n \) is a Fibonacci number if and only if one (or both) of the following conditions is true:
1. \( 5n^2 + 4 \) is a perfect square.
2. \( 5n^2 - 4 \) is a perfect square.
This property provides a direct and efficient way to check for Fibonacci numbers without generating the entire Fibonacci sequence.
Below is a Python function that implements this logic:
import math
def is_perfect_square(x):
"""Check if a number x is a perfect square."""
s = int(math.sqrt(x))
return s * s == x
def is_fibonacci(n):
"""Check if the number n is a Fibonacci number."""
# A Fibonacci number must be a non-negative integer
if n < 0:
return False
# Check the two conditions
return is_perfect_square(5 * n * n + 4) or is_perfect_square(5 * n * n - 4)
# Example usage
number = 21
if is_fibonacci(number):
print(f"{number} is a Fibonacci number.")
else:
print(f"{number} is not a Fibonacci number.")
Explanation of the Code
1. is_perfect_square Function: This helper function checks if a given number \( x \) is a perfect square by taking the integer square root and verifying if squaring it returns the original number.
2. is_fibonacci Function:
- It starts by checking if the input number \( n \) is non-negative, as Fibonacci numbers are non-negative integers.
- The function then uses the mathematical conditions to check if either \( 5n^2 + 4 \) or \( 5n^2 - 4 \) is a perfect square, returning True if either condition is met, indicating that \( n \) is a Fibonacci number.
Usage
Using this function makes checking for Fibonacci numbers straightforward and efficient, suitable for integration into larger applications or for standalone use in mathematical explorations.