How to write the Fibonacci Sequence?

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!

The idea behind the Fibonacci sequence is shown in the following Python code:

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

This means that fib is a function that can do one of three things. It defines fib(1) == 1, fib(0) == 0, and fib(n) to be:

fib(n-1) + fib(n-2)

Where n is an arbitrary integer. This means that fib(2) for example, expands out to the following arithmetic:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

We can calculate fib(3) the same way with the arithmetic shown below:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

The important thing to realize here is that fib(3) can't be calculated without calculating fib(2), which is calculated by knowing the definitions of fib(1) and fib(0). Having a function call itself like the fibonacci function does is called recursion, and it's an important topic in programming.

This sounds like a homework assignment so I'm not going to do the start/end part for you. Python is a wonderfully expressive language for this though, so this should make sense if you understand math, and will hopefully teach you about recursion. Good luck!

Edit: One potential criticism of my code is that it doesn't use the super-handy Python function yield, which makes the fib(n) function a lot shorter. My example is a little bit more generic though, since not a lot of languages outside Python actually have yield.

We know that

And that The n-th power of that matrix gives us:

So we can implement a function that simply computes the power of that matrix to the n-th -1 power.

as all we know the power a^n is equal to

So at the end the fibonacci function would be O( n )... nothing really different than an easier implementation if it wasn't for the fact that we also know that x^n * x^n = x^2n and the evaluation of x^n can therefore be done with complexity O( log n )

Here is my fibonacci implementation using swift programming language:

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

This has complexity O( log n ). We compute the oìpower of Q with exponent n-1 and then we take the element m00 which is Fn+1 that at the power exponent n-1 is exactly the n-th Fibonacci number we wanted.

Once you have the fast fibonacci function you can iterate from start number and end number to get the part of the Fibonacci sequence you are interested in.

let sequence = (start...end).map(fibonacciFast)

of course first perform some check on start and end to make sure they can form a valid range.

I know the question is 8 years old, but I had fun answering anyway. :)

If you're a fan of recursion you can cache the results easily with the lru_cache decorator (Least-recently-used cache decorator)

from functools import lru_cache


@lru_cache()
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

If you need to cache more than 128 values you can pass maxsize as an argument to the lru_cache (e.g. lru_cache(maxsize=500). If you set maxsize=None the cache can grow without bound.

The fibonacci sequence if you don't know what that is basically you print out a number and each each number that you print out is the previous two numbers added together.

a, b = 0,1 
for i in range(0, 10):
    print(a)
    a, b = b, a + b

output:

0
1
1
2
3
5
8
13
21
34

So 0 and 1 if you add those together it equals 1 if you add 1 and 1 it equals 2 if you add 1 and 2 it equals 3 and it keeps going and keeps going.

Fibonacci sequence here that I've written using generators:

def fib(num): 
    a, b = 0,1 
    for i in range(0, num):
        yield "{}: {}".format(i+1, a)
        a, b = b, a + b
        
for item in fib(10):
    print(item)

output:

1: 0
2: 1
3: 1
4: 2
5: 3
6: 5
7: 8
8: 13
9: 21
10: 34

Fibonacci sequence that we went over before except now we have a function here yields and yield is the keyword that lets you know that it's a generator.

• So, it yields your result and then we can loop through the generator and print out each item.
• If we run through then we can see that it still works just like it worked before but now we're using generators instead which have more advantages over returning a list but there are times and when you wouldn't want to use generators.
• You need do to your research and figure out when you really do get those advantages from generators and when they may not be the best option for you.

Optimized function of finding Fibonacci by keeping list in memory

def fib(n, a=[0, 1]):
    while n > len(a):
        a.append(a[-1] + a[-2])
    return a[n-1]

print("Fibonacci of 50 - {}".format(fib(50))

It can be done by the following way.

n = 0

numbers = [0]

for i in range(0,11):
    print n,
    numbers.append(n)
    prev = numbers[-2]
    if n == 0:
        n = 1
    else:
        n = n + prev

Just for fun, in Python 3.8+ you can use an assignment expression (aka the walrus operator) in a list comprehension, e.g.:

>>> a, b = 0, 1
>>> [a, b] + [b := a + (a := b) for _ in range(8)]  # first 10 Fibonacci numbers
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

An assignment expression allows you to assign a value to a variable and return it in the same expression. Therefore, the expression

b := a + (a := b)

is equivalent to executing

a, b = b, a + b

and returning the value of b.

def fib(x, y, n):
    if n < 1: 
        return x, y, n
    else: 
        return fib(y, x + y, n - 1)

print fib(0, 1, 4)
(3, 5, 0)

#
def fib(x, y, n):
    if n > 1:
        for item in fib(y, x + y, n - 1):
            yield item
    yield x, y, n

f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55

Using append function to generate first 100 elements.

def generate():
    series = [0, 1]
    for i in range(0, 100):
        series.append(series[i] + series[i+1])

    return series


print(generate())

On the much shorter format:

def fibbo(range_, a, b):
    if(range_!=0):
        a, b = b, a+b
        print(a)
        return fibbo(range_-1, a, b)
    return

fibbo(11, 1, 0)

Doing this solution by calling function and modularized

def userInput():
    number = int(input('Please enter the number between 1 - 40 to find out the 
    fibonacci :'))
    return number

def findFibonacci(number):
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        return findFibonacci(number - 1) + findFibonacci (number - 2)


def main():
    userNumber = userInput()
    print(findFibonacci(userNumber))

main() 

Simple Fibo:

def fibo(start, count):
    a = [start, start+1]
    for i in range(count-len(a)):
        a.append(a[-1]+a[-2])
    return a
a = fibo(0, 10)
print 'fibo', a

OUTPUT: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Fibonacci written as a Generator:

# fill in this function
def fib():
    a = 1
    b = 1
    yield(a)
    yield(b)
    for i in range(2, 10):
        c = a+b
        a, b = b, c
        yield(c)
    #pass #this is a null statement which does nothing when executed, useful as a placeholder.

# testing code
import types
if type(fib()) == types.GeneratorType:
    print("Good, The fib function is a generator.")

    counter = 0
    for n in fib():
        print(n)
        counter += 1
        if counter == 10:
            break

well, there are many ways. I have made use of lists to solve this probelm.. below is the working code... feel free to comment if any feedback

def fib(n):
    if n == 0: #to start fibonacci seraries value must be >= 1
        print('Enter postive integer')
    elif n ==1:
        print(0)
    else:
        li = [0, 1]
        for i in range(2, n): # start the loop from second index as 'li' is assigned for 0th and 1st index
            li.append(li[-1] + li[-2])
            i += 1
        print(*li)  # '*' is used to print elements from list in single line with spaces

n = int(input('Enter the number for which you want to generate fibonacci series\n'))
fib(n)

def fib(n):
    """
    n >= 1, the number of elements in the Fibonacci sequence
    """
    x, y = 0, 1
    for i in range(n):
        yield x
        x, y = y, x + y

These are two implementations of sequence calculation. First implementation uses polynomial calculation using golden ratio. The second uses conventional sequence calculation with memo creation.

from unittest import TestCase
from math import pow, sqrt
import unittest


GOLDEN_RATIO = 1.618034
    

def fib_low_memory(n):
    return (pow(GOLDEN_RATIO, n) - pow(1 - GOLDEN_RATIO, n))/ sqrt(5)


def fib(n):
    memo = [0, 1, 1]
    if n == 0:
        return 0
    if n == 1:
        return 1

    while len(memo) <= n:
        e = memo[-1]
        memo.append(memo[-1] + memo[-2])
    return memo[-1]



class TestFibonnaci(TestCase):
    def test_6(self):
        self.assertEqual(fib(6), 8)

    def test_low_memory_6(self):
        self.assertEqual(int(fib_low_memory(6)), 8)

    def test_12(self):
        self.assertEqual(fib(12), 144)

    def test_low_memory_12(self):
        self.assertEqual(int(fib_low_memory(12)), 144)




if __name__ == '__main__':
    unittest.main()

The fibonacci sequence can be coded as follows.

n = int(input('Length: '))

def fibonacci(n):
    a, b = 0, 1
    for i in range(n):
        print(a)
        a, b = b, a+b


fibonacci(n)

Output:

Length: 5
0
1
1
2
3

This is similar to what has been posted, but it's clean, fast, and easy to read.

def fib(n):
# start with first two fib numbers
fib_list = [0, 1]
i = 0
# Create loop to iterate through n numbers, assuming first two given
while i < n - 2:
    i += 1
    # append sum of last two numbers in list to list
    fib_list.append(fib_list[-2] + fib_list[-1])
return fib_list

Simple def -- try this..

def fib(n):
    first = 0
    second = 1
    holder = 0
    array = []
    for i in range(0, n):
      first = second
      second = holder
      holder = first + second
      array.append(holder)
    return array

input -> 10
output -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

# num is the number up to which your list will go
#first I created a list, and I wanted to code #everything, but obviously, I could have typed l = [0,1]

def fab(num):

    l = []
    for k in range(0,2):
        l.append(k)

    while l[-1]<num:
        x = l[-1]+l[-2]

        if x>=num:
            break
        else:
            l.append(x)

    return l

Fibonacci series in python,by creating null list:

                   inp=int(input())     #size of the series example it is 7
                   n=0
                   n1=1
                   x=[]                 #blank list
                   x.insert(0,0)    #initially insert 0th position 0 element
                   for i in range(0,inp-1):
                    nth=n+n1
                    n=n1                  #swapping the value
                    n1=nth
                    x.append(n)          #append all the values to null list
                   for i in x:        #run this loop so ans is 0 1 1 2 3 5 8
                    print(i,end=" ")

Simple Fibonacci Sequence:

def fib(x):
    b = 1
    c = 0
    print(0)
    for i in range(x - 1):
        a = b
        b = c
        c = a + b
        print(c)