Recursion Formula for Integer Partitions

Question

I have written the following code for evaluating integer partitions using the recurrence formula involving pentagonal numbers:

def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while ((n >= (k*(3*k-1)/2)) or (n >= (k*(3*k+1)/2))):
            i = (k * (3*k-1)/2)
            j = (k * (3*k+1)/2)
            if ((n-i) >= 0):
                p -= ((-1)**k) * part(n-i)
            if ((n-j) >= 0):
                p -= ((-1)**k) * part(n-j)
            k += 1
    return p

    n = int(raw_input("Enter a number: "))
    m = part(n)
    print m

The code works fine up until n=29. It gets a bit slow around n=24, but I still get an output within a decent runtime. I know the algorithm is correct because the numbers yielded are in accordance with known values.

For numbers above 35, I don't get an output even after waiting for a long time (about 30 minutes). I was under the impression that python can handle numbers much larger than the numbers used here. Can someone help me improve my runtime and get better results? Also, if there is something wrong with the code, please let me know.

Padraic Cunningham · Accepted Answer · 2015-12-22T18:59:21.920

4

You can use Memoization:

def memo(f):
    mem = {}
    def wrap(x):
        if x not in mem:
            mem[x] = f(x)
        return mem[x]
    return wrap

@memo
def part(n):
    p = 0
    if n == 0:
        p += 1
    else:
        k = 1
        while (n >= (k * (3 * k - 1) // 2)) or (n >= (k * (3 * k + 1) // 2)):
            i = (k * (3 * k - 1) // 2)
            j = (k * (3 * k + 1) // 2)
            if (n - i) >= 0:
                p -= ((-1) ** k) * part(n - i)
            if (n - j) >= 0:
                p -= ((-1) ** k) * part(n - j)
            k += 1
    return p

Demo:

In [9]: part(10)
Out[9]: 42

In [10]: part(20)
Out[10]: 627

In [11]: part(29)
Out[11]: 4565

In [12]: part(100)
Out[12]: 190569292

With memoization we remember previous calculation so for repeated calculations we just do a lookup in the dict.

edited Dec 22 '15 at 18:59

answered Dec 22 '15 at 18:04

Padraic Cunningham

176,452
29
245
321

for n=500, I'm getting a runtime error saying maximum recursion depth exceeded. Is there any way around this? – Nannu Dec 22 '15 at 18:41
@Nannu, you can increase the recursion limit but really you would be better off implementing it iteratively. Python is not optimised for recursion – Padraic Cunningham Dec 22 '15 at 18:45
I can get to n =999, anything after that blows the stack – Padraic Cunningham Dec 22 '15 at 18:51
I understand that recursion isn't really the best way to go in python, but I want to obtain the answers using recursion; I have another formula that doesn't use recursion, so I want to compare. Can you explain how increase the recursion limit? – Nannu Dec 22 '15 at 18:57
Yeah, I got upto n=500 until I got the error. This was after memoizing the function – Nannu Dec 22 '15 at 18:58
Were you able to get to n=999 without altering the recursion depth? – Nannu Dec 22 '15 at 19:01
@Nannu, yes, `23127843459154899464880444632250L`, To increase `import sys; sys.setrecursionlimit(n)`, the default is 1000, for me `sys.setrecursionlimit(5000)` I can do`part(9999) -> 5709901879704736738758549207052696680819022123397567612860179055188265961723158018938110612668644192313000L` https://docs.python.org/2/library/sys.html#sys.setrecursionlimit the limit is platform dependant – Padraic Cunningham Dec 22 '15 at 19:01
I have used sys.setrecursionlimit(50000) (I read somewhere that the hard recursion limit is 2**31 -1 on Linux), but for n=14031, I got the following message: segmentation fault (core dumped). What does this mean? – Nannu Dec 22 '15 at 19:28
A segfault is from trying to access memory somewhere you shouldn't be, there are more factors involved than just setting the recursion limit. – Padraic Cunningham Dec 22 '15 at 19:35

score 0 · Answer 2 · answered Dec 22 '15 at 18:45

Well there are a number of things you can do.

Remove duplicate calculations. - Basically you are calculating "3*k+1" many times for every execution of your while loop. You should calculate it once and assign it to a variable, and then use the variable.
Replace the (-1)**k with a much faster operation like something like -2*(k%2)+1). So instead of the calculation being linear with respect to k it is constant.
Cache the result of expensive deterministic calculations. "part" is a deterministic function. It gets called many times with the same arguments. You can build a hashmap of the inputs mapped to the results.
Consider refactoring it to use a loop rather than recursion. Python does not support tail recursion from what I understand, thus it is burdened with having to maintain very large stacks when you use deep recursion.

If you cache the calculations I can guarantee it will operate many times faster.

I think the caching optimisation is pretty apparent from my answer, an iterative solution would probably be the only way to really improve the OP's own code outside of caching — Padraic Cunningham, Dec 22 '15 at 18:47
@Adam, I understand that recursion isn't really the best way to go in python, but I want to obtain the answers using recursion; I have another formula that doesn't use recursion, so I want to compare. — Nannu, Dec 22 '15 at 18:56

Recursion Formula for Integer Partitions

2 Answers2