We all know how the Fibonacci numbers are defined: the n^{th} Fibonacci number is equal to the sum of the two before it, with initial conditions F_{1} = F_{2} = 1. Translated into ~~my~~ mathematical language, that is:

F_{n} = F_{n – 1} + F_{n – 2}

This is an example of a recurrence relation.

Using the theory of generating functions we can turn this recurrence relation into a “closed-form” or explicit formula:

[This book taught me generating functions – it’s awesome! You can buy it from that link and earn me a coffee :D]
Here, that odd-looking symbol φ (shame on you) is the magical Golden Ratio (read up on it!), equal to:

Oh, another thing. The number of digits in a number is equal to the ceiling of its logarithm in base 10. Here’s why.

Manipulating these leads us to an expression for the index of the first Fibonacci number with *d* digits:

F_{n} = (*d* − 1 + log_{10}(5) /2) / log_{10}(φ)

And with that, here’s the two lines of *code*! (Code!) (OMG *code*!)

from math import log10, sqrt, ceil
print(int(ceil((999 + log10(5)/2.0) /
log10((1 + sqrt(5))/2.0))))

And that’s how I became the 70181st person to solve this problem!

[image credit: Wikimedia]
### Like this:

Like Loading...

*Related*