Published on

# Python: Writing the perfect Tribonacci sequence

Authors
•  Name
Njuguna Mureithi
@tweetofnjuguna

## Not Fibonacci, Tribonacci

A Fibonacci sequence function in python below:

``````def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print(fib(5))
``````

A Tribonacci sequences occur in several ways:

abcSequence
0010, 1, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, …
1111, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, …
0100, 1, 0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, …
3133, 1, 3, 7, 11, 21, 39, 71, 131, 241, 443, 815, …
-122-1, 2, 2, 3, 7, 12, 22, 41, 75, 138, 254, 467, …

Now, Apart from creating a function that can handle any sequence, the function was also supposed to calculate huge numbers. I decided to start with a simple if loop.

## Simplest Approach

``````def fib3(n):
# maximum recussion error for 4000
if n == 0:
return 1
elif n == 1:
return 1
elif n == 2:
return 1
else:
return fib3(n-1) + fib3(n-2) + fib3(n-3)
``````

This worked for small Tribonacci calculations, but had a maximum recussion error. My second instinct was to memorize.

## Memorize

``````memory = {0:1, 1:1, 2:1}

def fib3_alternative(n):
# maximum recussion error for 4000; Avoided by building up results in memory
if not n in memory:
memory[n] = fib3_alternative(n-1) + fib3_alternative(n-2) + fib3_alternative(n-3)
return memory[n]
``````

This would work but only if I build the memory slowly:

Building the memory

``````#to avoid maximum recussion errors in python, we have to smartly build our fib3 memory
fib3_alternative(40)
fib3_alternative(100)
fib3_alternative(300)
fib3_alternative(700)
fib3_alternative(1000)
fib3_alternative(1500)
fib3_alternative(2000)
fib3_alternative(2500)
fib3_alternative(3000)
fib3_alternative(3500)
print("Fib3_alternative for 4000 is {}".format(fib3_alternative(4000)))
I had to create something that would work for all sequences, and must have no complicated methods.
``````

After several times of trial and error, It came to me:

### Queueing

``````def fib3_best(n):
queue = [1, 1, 1]
for i in xrange(n-2):
queue = queue[1:] + [sum(queue)]
return queue[-1]
print ("Fib3_best for 4000 is {}".format(fib3_best(4000)))
``````

This works like a charm! You can change queue to whichever sequence you feel suits you.