As with the previous post, this post is a spinoff of a blog post by Brian Hayes. He considers the problem of determining whether a number *n* is a Fibonacci number and links to a paper by Gessel that gives a very simple solution: A positive integer *n* is a Fibonacci number if and only if either 5*n*^{2} – 4 or 5*n*^{2} + 4 is a perfect square.

If we know *n* is a Fibonacci number, how can we tell which one it is? That is, if *n* = *F*_{m}, how can we find *m*?

For large *m*, *F*_{m} is approximately φ^{m} / √ 5 and the error decreases exponentially with *m*. By taking logs, we can solve for *m* and round the result to the nearest integer.

We can illustrate this with SymPy. First, let’s get a Fibonacci number.

>>> from sympy import * >>> F = fibonacci(100) >>> F 354224848179261915075

Now let’s forget that we know *F* is a Fibonacci number and test whether it is one.

>>> sqrt(5*F**2 - 4) sqrt(627376215338105766356982006981782561278121)

Apparently 5*F*^{2} – 4 is not a perfect square. Now let’s try 5*F*^{2} + 4.

>>> sqrt(5*F**2 + 4) 792070839848372253127

Bingo! Now that we know it’s a Fibonacci number, which one is it?

>>> N((0.5*log(5) + log(F))/log(GoldenRatio), 10) 100.0000000

So *F* must be the 100th Fibonacci number.

It looks like our approximation gave an exact result, but if we ask for more precision we see that it did not.

>>> N((0.5*log(5) + log(F))/log(GoldenRatio), 50) 99.999999999999999999999999999999999999999996687654

**Related posts**: