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:
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.