slinky773 - 6 months ago 50

Python Question

Project Euler Problem 25:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms

will be F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 =

21, F9 = 34, F10 = 55, F11 = 89, F12 = 144

The 12th term, F12, 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:

return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2) # recursive definition of Fib term

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

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

Here's a version that won't ever stackoverflow

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