Euler's pentagonal number function in python

Question

max = 200
max=max+2 ### due to the later code, it got offset by 2

P = [0]*max ### make a list of zeros, length max
P[0] = 1
P[1] = 1

print 0,":", P[0] ### print value for n = 0,1
print 1,":", P[1]

Psign = [0]*max ### make a list the same length as P, to store the signs

### apply Euler's pentagonal numbers formula

k = 1
index= k*(3*k-1)/2
while index <=max:
    Psign[index] = (-1)**k
    index = k*(3*k+1)/2
    if index<=max:
        Psign[index] = (-1)**k
    k=k+1
    index = k*(3*k-1)/2


for n in range(1,max+1):
    n=n+1
    P[n] = 0
    for i in range(0,n+1):
        i=i+1
        P[n] = P[n] - P[n-i]*Psign[i]
    print n,":",P[n]

So I've got this code which can gives answer to the Number of Partitions of n (up to 200 at the moment). However, since I adapted the code from here which was written in Mathematica. I'm not quite sure about the later part. Somehow this part messes up with my limit. So if I want to produce number of partitions for 25, I must set my max variable to 27.

I really hope someone can help me correct this

Cheers,

Alex

Answer 1

Python's list indexing is 0-based, so, for example, a list of length n can be indexed by the integers in 0 through n-1 inclusive. It cannot be indexed by n. So start here:

P = [0]*max ### make a list of zeros, length max

You want to refer to P[max] later, but the list is too short (by 1) for that. So change to:

P = [0] * (max + 1)

You need also similarly to change:

Psign = [0]*max ### make a list the same length as P, to store the signs

to:

Psign = [0] * (max + 1)

Next look at:

for n in range(1,max+1):
    n=n+1

That's bizarre - iterate directly over the values you want. Like replace those lines with:

for n in range(2, max + 1):

The same kind of strange thing is repeated next:

    for i in range(0,n+1):
        i=i+1

Again, replace that to iterate directly over the i values you want:

    for i in range(n+1):

Finally, get rid of the:

max=max+2 ### due to the later code, it got offset by 2

at the top. That was just hiding some (not all) of the consequences of making your lists too small to begin with.

After making all those changes, the program runs fine for me, ending normally with final output:

200 : 3972999029388

So you got all the hard parts right! You just messed up the easy parts - LOL ;-) Good job.

Another function

Just for interest, I'll include the function I use for this. While it looks quite different, it's really the same method, "optimized" in various ways. Enjoy :-)

def p4(n, _p=[1]):
    "Number of partitions of n."

    from math import sqrt

    def inner(n, _p=_p):
        k = int((sqrt(24*n+1)-1.) / 6.) + 1
        negative = not (k & 1)
        i = n - (k*(3*k+1) >> 1)
        assert i < 0
        s = 0
        if i + k >= 0:
            s = _p[i+k]
            if negative:
                s = -s
        assert i + 3*k - 1 >= 0
        for k in xrange(k-1, 0, -1):
            i += 3*k + 2
            negative = not negative
            t = _p[i] + _p[i + k]
            if negative:
                t = -t
            s += t
        assert i+k == n-1
        _p[n] = s

    if n < 0:
        raise ValueError("argument must be >= 0")
    oldlen = len(_p)
    if n >= oldlen:
        _p.extend([None] * (n - oldlen + 1))
        for nn in xrange(oldlen, n+1):
            inner(nn)
    return _p[n]

Then, e.g.,

>>> p4(200)
3972999029388L