Brute Force Solution for Project Euler 25

Question

Project Euler 25 objective :

The Fibonacci sequence is determined by the recurrence relation:

F _n = F _n-1 + F _n-2 , where F _{1 = 1} and F ₂ = 1. Therefore, the first 12 members 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 member of F ₁₂ is the first term containing three digits.

What is the first term in a Fibonacci sequence that contains 1000 digits?

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

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 works in linear time and with a constant memory area, you do not need a list to save them. Here's a recursive version (however, if n is large enough, it will be https://stackoverflow.com/a/168269/ )

 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 (as a result, around N calls for parameter N), unlike your solution, which calls itself twice (about 2 ^ N calls for parameter N).

Here is a version that will never use 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 this is fast enough:

 $ time python fibo.py 3364476487643178326662161200510754331030214846068006390656476... real 0m0.869s 

But calling fib until you get a big enough result is not perfect: the first numbers in a series are computed several times. You can calculate the following fibonacci number and check its size in one cycle:

 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

Use the binet formula . This is the fastest way to find Fibonacci numbers, and it does not use recursion.

Answer 3

Two things can be optimized with a little code change. These two things:

• You calculate each fibonacci number using the other two fibonacci numbers, which leads to exponential complexity (which explodes even if you only calculate one but a high fibonacci level).

• You do not remember any previous calculated Fibonacci numbers to calculate the next in your cycle.

Just remember all the calculated Fibonacci numbers as a private implementation detail in Fibonacci , and you will get rid of both performance problems. You can do this using a simple dynamic array to which you add the result if it has not been cached before.

Pseudo code (I do not speak Python, but this can be easily implemented):

 def Fibonacci(NthTerm): if (cache contains NthTerm) return cache[NthTerm] else FibValue = Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2) cache[NthTerm] = FibValue return FibValue 

This will result in a very limited return, since you only calculate the Nth fibonacci number if you already know (and cached) the number (N-1) -th.

This optimization works even if you need a Fibonacci number (for future problems), but in this particular case we know that we only need to remember the last two numbers, since we will no longer ask for the old numbers. Thus, you do not need a whole list of numbers, but only two that you “go over” for each step in your main loop. Something like

 f1, f2 = f2, f1 + f2 

inside the loop and type initialization

 f1, f2 = 1, 1 

will significantly replace your Fibonacci feature and its performance issues, but it limits you to this limited use case.

Answer 4

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

Answer 5

Why no one 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 calculates 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 as follows:

 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)))) 

It leads to exit

 The 4782-th term has 1000 digits 

The generator computes the sequence and produces 1-by-1 terms, and this decision is almost instantaneous.

Answer 6

Instead of recursively calculating each term each time, create an array of terms, you can calculate the term by adding the terms [-1] and the terms [-2]

Answer 7

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; }