1

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)
Ludwig Wallin
  • 45
  • 1
  • 6
  • Okay, you're halfway there. What's the exact problem you're facing? I mean, comparing the current Fibonacci number to 1 million can't be that hard – ForceBru Feb 02 '19 at 15:10
  • So you want to find the Fibonacci below 1 million? or the first Fibonacci above million? – Ghantey Feb 02 '19 at 15:10
  • The first fibonacci number ABOVE one million. I know from testing that it is 1,346,269. Just don't know how to calculate it – Ludwig Wallin Feb 02 '19 at 15:14

2 Answers2

2

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)
trincot
  • 317,000
  • 35
  • 244
  • 286
  • Oh forgot to add that it has to be a recursive function. Can't use iteration – Ludwig Wallin Feb 02 '19 at 15:12
  • A recursive function is not a good idea for 1million as your code would reach the maximum recursion depth. Please read [this answer](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) to understand why iteration should be used. – amanb Feb 02 '19 at 15:21
  • Yeah after some digging around I found out that by myself but in the course we are currently working with recursion and I have code it with recursion – Ludwig Wallin Feb 02 '19 at 15:26
  • @trincot, its for the OP. Of course, your answer is right. – amanb Feb 02 '19 at 15:26
  • Really appreciate your answer and advise though :) – Ludwig Wallin Feb 02 '19 at 15:27
0

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)
Mark
  • 90,562
  • 7
  • 108
  • 148