Non Brute Force Solution to Project Euler 25

You can write a fibonacci function that runs in linear time and with constant memory footprint, you don't need a list to keep them. Here's a recursive version (however, if n is big enough, it will just stackoverflow)

def fib(a, b, n):
    if n == 1:
        return a
    else: 
        return fib(a+b, a, n-1)


print fib(1, 0, 10) # prints 55

This function calls itself only once (resulting in around N calls for a parameter N), in contrast with your solution which calls itself twice (around 2^N calls for a parameter N).

Here's a version that won't ever stackoverflow and uses a loop instead of recursion:

def fib(n):
    a = 1
    b = 0
    while n > 1:
        a, b = a+b, a
        n = n - 1
    return a

print fib(100000)

And that's fast enough:

$ time python fibo.py 
3364476487643178326662161200510754331030214846068006390656476...

real    0m0.869s

But calling fib until you get a result big enough isn't perfect: the first numbers of the serie are calculated multiple times. You can calculate the next fibonacci number and check its size in the same loop:

a = 1
b = 0
n = 1
while len(str(a)) != 1000:
    a, b = a+b, a
    n = n + 1
print "%d has 1000 digits, n = %d" % (a, n)

Why hasn't anybody used generators for this? This is a brute force solution, but it is very quick:

def fibo():
    a = 0
    b = 1
    while True:
        yield b
        a,b = b,a+b

This gives a generator that computes the Fibonacci sequence. For example

f = fibo()
[next(f) for i in range(10)]

produces

[1,1,2,3,5,8,13,21,34,55]

Using this, we can solve the problem like so:

f = enumerate(fibo())
x = 0
while len(str(x)) < 1000:
    i,x = next(f)

print("The %d-th term has %d digits"%(i+1,len(str(x))))

This produces the output

The 4782-th term has 1000 digits

The generator computes the sequence and produces terms 1 by 1 and this solution runs nearly instantly.