Python partitioning function needs optimization

Question

While researching for a project euler exercise (#78), I've learned that in order to partition a number you can create a power series. From that series you can expand and use the terms coefficient to get the number of ways to partition a particular number.

From there, I've created this small function:

## I've included two arguments, 'lim' for the number you wish to partition and 'ways' a list of numbers you can use to partition that number 'lim'. ##

def stack(lim,ways):

    ## create a list of length of 'lim' filled with 0's. ##
    posi = [0] * (lim + 1)

    ## allow the posi[0] to be 1 ##
    posi[0] = 1

    ## double loop -- with the amount of 'ways'. ##
    for i in ways:
        for k in range(i, lim + 1):
            posi[k] += posi[k - i]

    ## return the 'lim' numbered from the list which will be the 'lim' coefficient. ##
    return posi[lim] 

>>> stack(100,[1,5,10,25,50,100])
>>> 293
>>> stack(100,range(1,100))
>>> 190569291
>>> stack(10000,range(1,10000))
>>> 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143L

This worked fine on relatively small partitions but, with not with this exercise. Are there ways to speed this up possibly with recursion or a faster algorithm? I've read some places that using pentagonal numbers is a way to help with partitions too.

Now I don't need to return the actually number on this problem but, check if it is evenly divisible by 1000000.

Update: I ended up using the pentagonal number theorem. I am going to be attempting to use the Hardy-Ramanujan asymptotic formula that Craig Citro had posted.

Answer 1

I haven't personally checked this fact recently, but the title of "fastest partition algorithm" is likely still held by the implementation in Sage. You can see it mentioned in the docs, or better yet simply skip to the source code. If you're looking for a discussion of ways to compute this number, the original thread leading to this implementation is definitely interesting. The source file for the implementation itself starts with some useful comments about the code.