Tag Archives: golden ratio

Find The First 1000-digit Fibonacci Number [Project Euler Problem 25]

We all know how the Fibonacci numbers are defined: the nth Fibonacci number is equal to the sum of the two before it, with initial conditions F1 = F2 = 1. Translated into my mathematical language, that is:

Fn = Fn – 1 + Fn – 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:Image

[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:

Image

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

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

Fn = (d − 1 + log10(5) /2) / log10(φ)

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]
Advertisements