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 5n2 – 4 or 5n2 + 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 = Fm, how can we find m?
For large m, Fm 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 5F2 – 4 is not a perfect square. Now let’s try 5F2 + 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