Non Brute Force Solution to Project Euler 25

Question

Project Euler problem 25:

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F_{1 = 1} and F₂ = 1. Hence the first 12 terms will be F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

I made a brute force solution in Python, but it takes absolutely forever to calculate the actual solution. Can anyone suggest a non brute force solution?

def Fibonacci(NthTerm):
    if NthTerm == 1 or NthTerm == 2:
        return 1 # Challenge defines 1st and 2nd term as == 1
    else:  # recursive definition of Fib term
        return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)

FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary range
    FibValue = str(Fibonacci(Term)) # Convert integer to string for len()
    if len(FibValue) == 1000:
        FirstTerm = Term
        break # Stop there
    else:
        continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."

Answer 1

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)

Answer 2

Instead of recursively calculating every term each time, make an array of terms, then you can calculate a term by adding terms[-1] and terms[-2]

Answer 3

Here is the Java version in constant space and linear time:

    static int q24(){
    int index = 3;
    BigInteger fn_2 = new BigInteger("1");
    BigInteger fn_1 = new BigInteger("1");
    BigInteger fn   = fn_1.add(fn_2);
    while(fn.toString().length()<1000){
        fn_2 = fn_1;
        fn_1 = fn;
        fn = fn_2.add(fn_1);
        index++;
    }       
    return index;
}

Answer 4

Use binet's formula. It's the fastest way to find Fibonacci numbers, and it doesn't use recursion.

Answer 5

you can use Memorization :

m={}

def fub(n):
     if n not in m:
        if n <= 2 :
           m[n] =  1
        else:
           m[n] =  fub(n-1) + fub(n-2)

     return m[n]

i=1
while len(str(fub(i))) != 1000:
   i+=1
print(i)

Answer 6

You can try to use newton's approximation method on binet's formula. The idea is to find a tangent line on the graph and use the x-intercept of that line to approximate the value of the zero of the graph.