How to Check if a given Number is Fibonacci number?

In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence:

1,1,2,3,5,8,13,21,34,55,89,144..

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

The question may arise whether a positive integer x is a Fibonacci number. This is true if and only if one or both of 5x^2+4 or 5x^2-4 is a perfect square. (Source: Wiki)

bool isPerfectSquare(int x)
{
    int s = sqrt(x);
    return (s*s == x);
}
 
// Returns true if n is a Fibonacci Number, else false
bool isFibonacci(int x)
{
    return isPerfectSquare(5*x*x + 4) ||
           isPerfectSquare(5*x*x - 4);
}

One Thought on “How to Check if a given Number is Fibonacci number?

  1. Stanley on June 16, 2016 at 10:58 pm said:

    I am a lecturer by profession.congratulations.
    glad to let you know tat you have a good and rare collection of puzzle. It will be a great help if you include more problems.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation