*917*

## Given a number ‘n’, how to check if n is a Fibonacci number.

A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘n’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not.

*A number is Fibonacci if and only if one or both of 5n ^{2}+4 or 5x^{2}-4 is a perfect square* (Source: Wikipedia). Following is a simple program based on this concept.

// C program to check if x is a perfect square #include <stdio.h> #include <math.h> // A utility function that returns 1 if x is perfect square int isPerfectSquare(int x) { int s = sqrt(x); if(s*s == x) return 1; else return 0; } // Returns 1 if n is a Fibonacci Number, else 0 int isFibonacci(int n) { // n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both // is a perfect square if(isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n - 4)) return 1; else return 0; } // A utility function to test above functions int main(void) { int i; for (i = 1; i <= 10; i++) { if(isFibonacci(i) printf("%d is a Fibonacci Number \n",i); else printf("%d is not a Fibonacci Number. \n",i); } return 0; }

Output:-

1 is a Fibonacci Number

2 is a Fibonacci Number

3 is a Fibonacci Number

4 is not a Fibonacci Number

5 is a Fibonacci Number

6 is not a Fibonacci Number

7 is not a Fibonacci Number

8 is a Fibonacci Number

9 is not a Fibonacci Number

10 is not a Fibonacci Number