A partition of an integer `n`

is defined as a way of representing `n`

as a sum of positive integers where the order of the summands does not matter ([1]). The partition function `p(n)`

denotes the number of possible partitions of `n`

. For example, 5 can be represented in 7 different ways:

5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1

So, `p(5) = 7`

. The value of p(n) grows very quickly as `n`

grows. For example:

p(10) = 42 p(50) = 204226 p(100) = 190569292 p(500) = 2300165032574323995027 p(1000) = 24061467864032622473692149727991 p(5000) = 169820168825442121851975101689306431361757683049829233322203824652329144349 p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144 p(25000) = 795153665211854316623270592370059262051214684698263936645288037606040374321677412443089599487464373732598268996277510779455269671090533346705889153124159897638140712684550 p(50000) = 3626186097141667844592140891595633728165383082527785049015872755414109904256712082718122747316610565824630881772910217544261659239432670671532413858378256188987333877121891586607957389750538447474712592979263719012461858719791627302489739548263

Though there is a very easy recursive solution to find `p(n)`

by using an intermediate function ([4]), this method is not much suitable for large values of `n`

.

Surprisingly, `p(n)`

can be calculated by using a simple recursive function: ([3])

p(n) = 0 for n < 0 p(0) = 1 p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - p(n - 22) - p(n - 26) + ...

At first this equation looks like a total chaos due to the sequence `1, 2, 5, 7, 12, 15, 22, 26, ...`

, but that is generalized Pentagonal Number sequence([2]) which is defined by:

f(k) = k(3k - 1) / 2 for k = 0, 1, -1, 2, -2, 3, -3, 4, -4, ...

Well, I am not going to prove this relation between integer partition function and pentagonal numbers here, but if anyone is really really interested then try Google and good number theory books.

Thus `p(n)`

can be written simply as:

Finally here is a simple (read it, stupid and not optimized) Python program that exploits the relation between partition function and pentagonal numbers and generates partition values.

import sys p = [1] def generate(n): for i in range(1, n + 1): s = 0 k = 1 while True: f = i - k * (3 * k - 1) / 2 if f < 0: break if k % 2: s += p[f] else: s -= p[f] f = i - k * (3 * k + 1) / 2 if f < 0: break if k % 2: s += p[f] else: s -= p[f] k += 1 p.append(s) def main(): generate(int(sys.argv[1])) for i in range(len(p)): print i, p[i] if __name__ == '__main__': main()

$ python partition.py 20 0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 56 12 77 13 101 14 135 15 176 16 231 17 297 18 385 19 490 20 627

Here is a file containing the partition values upto 50000. You can have a look if you are interested (warning: the file is big).

Like always, any feedback is welcome.

[1] Integer Partition

[2] Pentagonal Number

[3] Playing with Partitions on the Computer

[4] Intermediate function

Pingback: Integer Partition in Java | Off Topic…Sharing stuffs

Thanks Taskinoor for this post. Here goes one supplementary post in response of this: http://azimbabu.wordpress.com/2011/11/21/integer-partition-java/ ;)