Let me preface it with that I am new to python completely and programming for that matter and I need to create a program to print all Catalan numbers up to one trillion. I have the basics of the program written out but I can't seem to understand why I'm not getting the right numbers. Also I am running into programs when trying to graph the trend out. Thanks in advance and here is the code I have:
import numpy as np
import scipy as sp
from pylab import *
def Catalan(n):
if n==0:
return (1)
elif n==1:
return (1)
else:
return ((4*n+2)/(n+2))*Catalan(n-1)
for n in range(18):
print (Catalan(n))
n=np.linspace(0,18,100)
y=Catalan(n)
plot(n,y,'r')
show()
There are two main mistakes in your Catalan function.
First, as seen in http://en.wikipedia.org/wiki/Catalan_number, the formula you wrote is useful to compute Catalan(n+1) in terms of Catalan(n). To use it to compute Catalan(n) in terms of Catalan(n-1), as you do, you must shift the index. So it should be (4*n-2)/(n+1)*Catalan(n-1).
Second, python uses integer arithmetic when dealing with ints. So, the quotients get rounded down to ints (this is, 5/2 gives 2, not 2.5). One way to deal with this is to write first the product and then the quotient: (4*n-2)*Catalan(n-1)/(n+1).