CODEWITHSUNDEEP
pythonpython-3.xfibonacci
Ludwig Wallin
Ludwig Wallin

Reputation: 45

Find the first fibonacci number above 1 million

Currently taking a programming course and got as an assignment to find the first fibonacci number above a million and I'm having a bit of trouble finding the specific number. I'm also supposed to be finding the index of the n:th number when it hits 1 million. I'm pretty new to coding but this is what I've come up with so far, just having a hard time to figure out how to actually calculate what the number is.

I guess you would switch out the for-with a while-loop but haven't figured out it how to get it all to work.

Thanks in beforehand :) 

def fib_seq(n):
    if n <= 2:
       return 1
    return fib_seq(n-1) + fib_seq(n-2)


lst = []
for i in range(1, 20):
    lst.append(i)
    print(fib_seq(i), lst)

Upvotes: 1

Views: 677

Answers (2)

Mark
Mark

Reputation: 92460

If you need to do this with some find of recursion, you should try to avoid calling the recursions twice with each iteration. This is a classic example where the complexity explodes. One way to do this is to memoize the already calculated results. Another is to maintain state with the function arguments. For example this will deliver the answer and only call the function 32 times:

def findIndex(v, prev = 0, current = 1, index = 0):
    if v < prev:
        return (prev, index)
    return findIndex(v, current, prev+current, index + 1 )


findIndex(1000000)  # (1346269, 31)

Upvotes: 0

trincot
trincot

Reputation: 350771

Some points:

  • You don't need to build a list. You're only asked to return an index and the corresponding Fibonnacci number.

  • The recursive algorithm for Fibonnacci is not best practice, unless you would use some memoization. Otherwise the same numbers have to be recalculated over and over again. Use an iterative method instead.

Here is how that could look:

def fib(atleast):
    a = 0
    b = 1
    i = 1
    while b < atleast:
        a, b = b, a+b
        i += 1
    return i, b


print(fib(1000000)) # (31, 1346269)

Upvotes: 2

Related Questions