Partition Numbers
April 15, 2011
The partition-number function P(n) gives the number of ways of writing n as the sum of positive integers, irrespective of the order of the addends. For instance P(4) = 5, since 4 = 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1. Sloane’s A000041 gives the first ten partition numbers as 1, 2, 3, 5, 7, 11, 15, 22, 30, and 42; the numerous references to that sequence point to many fascinating facts about partition numbers, including their close association with pentagonal numbers. By convention, P(0) = 1 and P(n) = 0 for negative n. Partition numbers are normally calculated by the formula, which was discovered by Leonhard Euler:
![P(n) = \sum_{k=1}^n (-1)^{k+1} \left[ P\left( n - \frac{k\left(3k-1\right)}{2} \right) + P\left( n - \frac{k\left(3k+1\right)}{2} \right) \right]](https://s0.wp.com/latex.php?latex=P%28n%29+%3D+%5Csum_%7Bk%3D1%7D%5En+%28-1%29%5E%7Bk%2B1%7D+%5Cleft%5B+P%5Cleft%28+n+-+%5Cfrac%7Bk%5Cleft%283k-1%5Cright%29%7D%7B2%7D+%5Cright%29+%2B+P%5Cleft%28+n+-+%5Cfrac%7Bk%5Cleft%283k%2B1%5Cright%29%7D%7B2%7D+%5Cright%29+%5Cright%5D&bg=ffffff&fg=555555&s=0&c=20201002)
Your task is to write a function that computes P(n), and to calculate P(1000). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 