Partition function

Partition function P(n)

The partition function P(n) represents the number of possible partitions of a non-negative integer n. The values of this function for n = 1, 2, 3, ... are:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence A000041 in the OEIS).

---

According to the Pentagonal number theorem, the mentioned identity implies a marvellous recurrence for calculating P(n).
.
or

Where G is the generalized pentagonal numbers sequence.

Code - O(N^1.5)

This following MES topic suggested a simple method for computing P(n) in O(N^1.5) time-complexity.

const ll MOD=1e9+7;
const int N=2e5+5;
ll p[N];
vector<ll> pentagonal;

void compute_p_function(int MX){
	for(int i=1;i<MX;++i) pentagonal.push_back(i),pentagonal.push_back(-i);
	transform(pentagonal.begin(),pentagonal.end(),pentagonal.begin(),[](ll k){return k*(3LL*k-1LL)/2LL;});
	p[0]=1;p[1]=1;p[2]=2;
	for(int i=3;i<MX;++i)
		for(int j=0;j<(int)pentagonal.size()&&pentagonal[j]<=i;++j)
			if(j%4<2) p[i]=(p[i]+p[i-pentagonal[j]]%MOD)%MOD;else p[i]=(p[i]-p[i-pentagonal[j]]%MOD+MOD)%MOD;
}