Non Brute Force Solution to Project Euler 25

user_962128 0
Viewed 9056

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:  # 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."
fibonacci brute-force python
8 Answers

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.

user_49276160

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

If you are using Kotlin, a very simple solution.

import java.math.BigInteger
val bound: BigInteger = BigInteger.TEN.pow(999)
var index = 2
var fib = BigInteger.ONE
var prevFib = BigInteger.ONE
while (fib < bound) {
    prevFib = fib.also { fib += prevFib }
    index++
}
println(index)
user_22694660
Related