CODEWITHSUNDEEP
pythonnumpycatalan
mitlabence
mitlabence

Reputation: 33

What is wrong with this Python code about the Catalan numbers?

I'm new to Python. This is a homework problem, but it is tough as I only have a little experience in Java. The code is supposed to print the first Catalan-numbers using its recursive definition:

C(n + 1) = C(n) * (4n + 2) / (n + 2)

EDIT:

My current code looks like this, and the only remaining problem is to put all the C(n) numbers I get by this code in a txt using the savetxt() method.

import numpy

c = []
c.append(1)
for i in xrange(0,1000000000):
    c.append((4*i+2)*c[i]/(i+2))
    print (c[i])
    if c[i]>= 1000000000:
        break


numpy.savetxt("catalan",numpy.c_[i, c[i]])

After this last problem is solved, I will try some other versions suggested in the answers (like filling up an array of zeroes first).

Upvotes: 2

Views: 1070

Answers (5)

An3
An3

Reputation: 1

Wouldn't be easy if you use while?

C1,C2 = 1.0, 1.0
n=0
while C1<=1000000000:
    print(C1)
    C1,C2 = (((4*n+2)/(n+2)) * (C1)), C1
    n+=1

Upvotes: 0

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133988

This is almost an exact duplicate of Python:: "IndexError: list index out of range"; in there I proposed that instead of using the recurrence, one should just use the iterative formula to produce the Catalan numbers; in your case you are using the iterative approach, but are storing them to an array. My approach is quite memory efficient compared to creating an array to store all n Catalan numbers:

def catalans():
    C = 1
    n = 0
    while True:
        yield C
        C = 2 * (2 * n + 1) * C // (n + 2)
        n += 1

with open('catalan', 'w') as output:
    for n, C in enumerate(1, catalans()):
        print(n, C, file=output)
        if C >= 1000000000:
            break

Upvotes: 2

jonrsharpe
jonrsharpe

Reputation: 122095

You can get better use out of numpy by actually using an array (which also makes the code look more like I think you originally had it):

import numpy as np

def catalan(x):
    """Create an array of the first x 'Catalan numbers'."""
    c = np.zeros(x)
    c[0] = 1
    for n in xrange(x-1):
        c[n+1] = c[n] * ((4 * n) + 2) / (n + 2)
    return c

If you can come up with a non-recursive definition, you can speed this up significantly (see e.g. Is a "for" loop necessary if elements of the a numpy vector are dependant upon the previous element?). Note that these numbers get big fast, though (you can only fit the first 34 in a 64-bit integer)!

Upvotes: 1

Kxxvc
Kxxvc

Reputation: 1

for i in range(0, 1000000000):

This should work.

On your first iteration, you are trying to use c[1], but it doesn't exist. You only have a value for c[0], so the list index is out of range.

Upvotes: 0

ZekeDroid
ZekeDroid

Reputation: 7209

Index out of range. Your first i is equal to 1 but c only has one element, which is index 0. So just change the range to (0,1000000000).

By the way, don't use range, use xrange, it'll be faster and take less memory. When you use range, Python creates an array of that size. An array of size 1000000000 takes a ton of memory. Instead, xrange create an iterator so it takes much less memory.

Upvotes: 1

Related Questions