Test if a number is fibonacci

Solution 1:

A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion.

Hope this helps

Solution 2:

A positive integer ω is a Fibonacci number if and only if either 5ω² + 4 or 5ω² - 4 is a perfect square.

See The Fabulous Fibonacci Numbers for more.

Solution 3:

While several people point out the perfect-square solution, it involves squaring a Fibonacci number, frequently resulting in a massive product.

There are less than 80 Fibonacci numbers that can even be held in a standard 64-bit integer.

Here is my solution, which operates entirely smaller than the number to be tested.
(written in C#, using basic types like double and long. But the algorithm should work fine for bigger types.)

static bool IsFib(long T, out long idx)
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    idx    = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == T);
}

Parameter #2 is the "Index" into the Fibonacci sequence.
If the value to be tested, T is a Fibonacci number, then idx will be the 1-based index of that number in the Fibonacci sequence. (with one notable exception)

The Fibonacci sequence is 1 1 2 3 5 8 13, etc.
3 is the 4th number in the sequence: IsFib(3, out idx); will return true and value 4.
8 is the 6th number in the sequence: IsFib(8, out idx); will return true and value 6.
13 is the 7th number; IsFib(13, out idx); will return true and value 7.

The one exception is IsFib(1, out idx);, which will return 2, even though the value 1 appears at both index 1 and 2.

If IsFib is passed a non-Fibonacci number, it will return false, and the value of idx will be the index of the biggest Fibonacci number less than T.

16 is not a Fibonacci value.
IsFib(16, out idx); will return false and value 7.
You can use Binet's Formula to convert index 7 into Fibonacci value 13, which is the largest number less than 16.

Solution 4:

#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi