calculate catalan numbers up to a billion
<p>I'm new to python (and programming in general), I was asked in my class to calculate Catalan numbers up to a billion but the program I wrote for it is not working as intended.</p>

<pre><code>    from numpy import division 
    C=1
    n=0
    while C&lt;=10000000000:
        print (C)
        C=(4*n+2)/(n+2)*C
        n=n+1
</code></pre>

<p>This is what it prints</p>

<p>1,
1,
2,
4,
8,
24,
72,
216,
648,
1944,
5832,
17496,
52488,
157464,
472392,
1417176,
4251528,
12754584,
38263752,
114791256,
344373768,
1033121304,
3099363912,
9298091736,</p>

<p>As you can see from my fourth iteration onwards, I get the wrong number and I don't understand why.</p>

<p>EDIT:
The mathematical definition I used is not wrong! I know the Wiki has another definition but this one is not wrong.
Co=1, Cn+1 = (4*n+2)/(n+2)*Cn</p>

<h3>The problem</h3>

<p>Your mathematical definition of Catalan numbers is incorrect when translated into code.</p>

<p>This is because of operator precedence in programming languages such as Python.</p>

<p>Multiplication and division both have the same precedence, so they are computed left to right. What happens is that the division operation <code>(4*n+2)/(n+2)</code> happens before the multiplication with <code>C</code>. When <code>n</code> is 2, <code>2*(2*n+2)/(n+2)</code> becomes <code>10/4</code> which is <code>2</code> in integer arithmetic. <code>1*C</code> which is <code>2</code> at this stage, gives <code>4</code> instead of giving the expected <code>5</code>.
Once a number in the series is incorrect, being computed iteratively is incorrect.</p>

<hr>

<h3>A possible work around</h3>

<p>Here's the definition <a href="https://en.wikipedia.org/wiki/Catalan_number" rel="nofollow">Catalan Numbers</a></p>

<p><a href="http://i.stack.imgur.com/816F2.png" rel="nofollow"><img src="http://i.stack.imgur.com/816F2.png" alt="enter image description here"></a></p>

<p>Which means, the nth Catalan number is given by:</p>

<pre><code>import operator as op

def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer//denom


def catalan(n):
    return ncr(2*n, n)/(n+1)
</code></pre>

<p>This is not very efficient, but it is at least correct.</p>

<hr>

<h3>The right fix</h3>

<p>To compute the series, you can do, using the recursive formula.</p>

<p><a href="http://i.stack.imgur.com/BYSSY.png" rel="nofollow"><img src="http://i.stack.imgur.com/BYSSY.png" alt="enter image description here"></a></p>

<pre><code>N=1000000 # limit
C=1
for i in xrange(0, N+1):
    print i,C
    C = (2*(2*i +1)*C)/(i+2)
</code></pre>

<p>For the first few, it looks like this:</p>

<pre><code>0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
</code></pre>

python