Monthly Archives: September 2013

Remember those neighbours who turned a 3KHz sound on? Well, they did it again yesterday.

Enter my little 2.1 setup with a not-so-little subwoofer playing the live performance of Fear of the Dark at full volume.
They won’t do it again.

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]

Why the GIL is a Tough Nut to Crack

Jeff Knupp on http://www.jeffknupp.com/blog/2012/03/31/pythons-hardest-problem/

After holding off for a long time (due to the scourge of half-yearly exams), I’ve finally started learning Scheme!

“A dreamer is one who can only find his way by moonlight, and his punishment is that he sees the dawn before the rest of the world.”

Oscar Wilde