Home Misc How to check if a given number is Fibonacci number?

How to check if a given number is Fibonacci number?

by nikoo28
0 comment

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 5n2+4 or 5x2-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

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More