The relation between Integer Partition and Pentagonal Numbers

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

About these ads