How to write the Fibonacci Sequence?

Question

I had originally coded the program wrongly. Instead of returning the Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 should = only those numbers between 1 & 20), I have written for the program to display all Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 displays = First 20 Fibonacci numbers). I thought I had a sure-fire code. I also do not see why this is happening.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

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

print map(fib, range(startNumber, endNumber))

Someone pointed out in my Part II (which was closed for being a duplicate - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) that I need to pass the startNumber and endNumber through a generator using a while loop. Can someone please point me in the direction on how to do this? Any help is welcome.

---

I'm a learning programmer and I've run into a bit of a jumble. I am asked to write a program that will compute and display Fibonacci's Sequence by a user inputted start number and end number (ie. startNumber = 20 endNumber = 100 and it will display only the numbers between that range). The trick is to use it inclusively (which I do not know how to do in Python? - I'm assuming this means to use an inclusive range?).

What I have so far is no actual coding but rather:

• Write Fib sequence formula to infinite
• Display startNumber to endNumber only from Fib sequence.

I have no idea where to start and I am asking for ideas or insight into how to write this. I also have tried to write the Fib sequence forumla but I get lost on that as well.

Answer 1

There is lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resources to find (quickly if possible) what you need.

Write Fib sequence formula to infinite

In math, it's given in a recursive form:

In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

Go on on the sites I linked to you and will see this (on wolfram):

This one is pretty easy to implement and very, very fast to compute, in Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

An other way to do it is following the definition (from wikipedia):

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.

If your language supports iterators you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P Good luck and have fun!