Thursday, October 16, 2014

How to check if a given number is Fibonacci number

How to check if the given number is a Fibonacci number?

A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers.

Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...

If a number is given, a straight forward way to check if it is a Fibonacci number is to generate the numbers one by one until we get the required number or greater than that.

Here is the python code do that.

One more approach is based on a property of Fibonacci numbers
If 5*x2+4 or 5*x2-4 (or both) is a perfect square, we can conclude that it is a Fibonacci number. 

The C++ code is given below.