∑MathAdvanced

Partition Function

Key Points

•
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
•
Its generating function is $ $\sum_{n \geq 0}$ p(n) $x^{n}$ = $\prod_{k \geq 1}$ (1 - $x^{k}$ )^{-1}$, which encodes unlimited copies of each part size.
•
Euler’s pentagonal number theorem yields a fast recurrence for p(n) using generalized pentagonal numbers, giving an O(n $n$ ) algorithm.
•
A straightforward dynamic programming approach via coin change computes all p(0..n) in O( $n^{2}$ ) time.
•
The Hardy–Ramanujan formula provides an accurate asymptotic: $p(n) $\sim$ $\frac{1}{4 n 3}$ e^{ $π \frac{2 n}{3}$ }$.
•
Partitions into distinct parts are equinumerous with partitions into odd parts, a classic identity verified by generating functions.
•
For programming contests, compute p(n) modulo a prime (e.g., 1e9+7) and use the Euler recurrence for n up to 1e6.
•
Common pitfalls include counting ordered compositions, forgetting the base case p(0)=1, and mishandling signs in the Euler recurrence.

Prerequisites

→Generating functions (ordinary) — Understanding how products encode unlimited copies and how coefficients correspond to counts is essential for the partition generating function.
→Dynamic programming (knapsack variants) — The standard algorithms for computing p(n) are direct applications of unbounded and 0/1 knapsack DPs.
→Modular arithmetic — Partition numbers grow extremely fast; contest implementations compute p(n) modulo a prime to avoid overflow.
→Asymptotic analysis — Interpreting the Hardy–Ramanujan estimate and comparing algorithmic complexities require comfort with asymptotics.
→Series manipulation and identities — Euler’s pentagonal number theorem and related identities are manipulations of infinite products and sums.
→Basic number theory — Concepts like divisibility, parity (odd/even parts), and integer properties arise in restricted partition problems.

Detailed Explanation

Tap terms for definitions

01Overview

The partition function p(n) counts the number of ways to write the integer n as a sum of positive integers, ignoring order. For example, p(4)=5 because 4, 3+1, 2+2, 2+1+1, and 1+1+1+1 are the only unordered sums of 4. This counting problem is central in number theory and combinatorics and has deep connections with q-series, modular forms, and representation theory. Computationally, p(n) appears in programming contests and algorithmic problems that reduce to counting solutions with unlimited copies of items (unbounded knapsack). The key tool is the generating function: the formal power series whose coefficient of x^n equals p(n). Euler discovered that the product over all k of (1 − x^k)^{-1} expands to the partition numbers. From this, he derived the pentagonal number theorem, which yields a surprisingly efficient recurrence based on generalized pentagonal numbers. Much later, Hardy and Ramanujan found an asymptotic formula that accurately estimates p(n) for large n, revealing its rapid growth is roughly exponential in (\sqrt{n}). In practice, we compute p(n) exactly modulo a large prime using dynamic programming or Euler’s recurrence, and we use asymptotics for estimates or sanity checks.

02Intuition & Analogies

Imagine you have limitless stacks of coins labeled by their values: 1, 2, 3, and so on. A partition of n is simply a way to pay n using these coins, where we don’t care about the order of payment—5 = 2+3 is the same as 3+2. The generating function acts like a vending machine for combinations: for each coin value k, the factor (1 + x^k + x^{2k} + x^{3k} + …) lists taking 0, 1, 2, 3, … coins of value k. Multiplying all these factors for k=1,2,3,… allows every possible combination to appear exactly once in the expansion. The coefficient next to x^n counts how many ways we can reach the total n—this is p(n). Euler’s pentagonal insight is like sorting the chaos of the huge product into a neat alternating pattern. He discovered that if you invert (\prod_{k\ge1} (1 - x^k)), the inverse series has coefficients supported at very special indices: the generalized pentagonal numbers 1, 2, 5, 7, 12, 15, …. Even better, the signs follow a +, +, −, −, +, +, … rhythm. This turns the huge product into a compact recurrence: to compute p(n), you peek back at previous values p(n−1), p(n−2), p(n−5), p(n−7), …. Each look-back is either added or subtracted according to that sign pattern. It’s like hiking up a mountain where each step uses a few carefully chosen previous steps instead of all of them. Finally, the Hardy–Ramanujan approximation is a ‘thermometer’ telling us how big p(n) should be for large n. It says p(n) grows almost like (e^{\pi \sqrt{2n/3}}) divided by a polynomial in n. This explains why exact values explode so quickly and why we often work modulo a number in code.

03Formal Definition

Let p(n) denote the number of integer partitions of n, with the convention p(0)=1 and p(n)=0 for

n < 0

. A partition of n is a multiset of positive integers whose sum is n. The ordinary generating function is \[

\sum_{n = 0}^{\infty}

p(n)

x^{n}

\prod_{k = 1}^{\infty}

\frac{1}{1 - x ^{k}}

. \] Euler’s pentagonal number theorem gives the identity \[

\prod_{k = 1}^{\infty}

(1 -

x^{k}

) =

\sum_{m = - \infty}^{\infty}

(-1)^m

x^{m (3 m - 1) /2}

. \] Combining these yields the recurrence (with p(0)=1): \[ p(n) =

\sum_{k = 1}^{\infty}

(-1)^{k-1}

\big

( p(n -

g_{k}

) + p(n - g'_k)

\big

), \] where \(

g_{k}

\frac{k ( 3 k - 1 )}{2}

\), \(g'_k =

\frac{k ( 3 k + 1 )}{2}

\), and terms with negative indices are zero. The number of terms for fixed n is \(O(

n

)\) because \(

g_{k}

\) grows quadratically in k. Asymptotically, Hardy and Ramanujan proved \[ p(n)

\sim

\frac{1}{4 n 3}

exp

\Big

(

π

\frac{2 n}{3}

\Big

), \] meaning the ratio of p(n) to the right-hand side tends to 1 as \(n

\to

\infty

\). There are exact convergent series (Rademacher’s formula) that compute p(n) in \(O(

n^{1/2 + ε}

)\) terms but are more intricate to implement.

04When to Use

Use the O(n^2) dynamic programming (unbounded knapsack) when n is up to ~2e4–1e5 and you need all p(0..n) modulo some MOD; it is simple, robust, and amenable to constraints like ‘at most k’ or ‘distinct parts’ by changing the loop order. Use Euler’s O(n\sqrt{n}) recurrence when n is as large as 1e6 (or more) and memory is tight; it computes p(n) from previous values with a small per-n workload. Prefer modulus arithmetic when exact integers would overflow—p(1000) already has 32 digits. For problems about restricted partitions, pick the right generating function: distinct parts uses (\prod (1+x^k)), odd parts uses (\prod (1-x^{2k-1})^{-1}), and ‘at most k parts’ uses a 2D DP with a cap on part count. When only an estimate is needed (e.g., bounding answers, sanity checks, or ordering by growth), use the Hardy–Ramanujan approximation. In competitive programming, precompute all p(0..N) once using Euler’s recurrence with MOD and answer multiple queries in O(1).

⚠️Common Mistakes

• Confusing partitions with compositions: compositions count ordered sums; partitions do not. For example, 3=2+1 and 3=1+2 are the same partition but different compositions. • Forgetting p(0)=1: there is exactly one partition of 0 (the empty sum), crucial as the DP base case and for the Euler recurrence. • Wrong loop order in DP: for ‘unlimited copies’ (part sizes can repeat), iterate sums increasing; for ‘distinct parts’ (each part at most once), iterate sums decreasing. Mixing these leads to counting ordered solutions or overcounting. • Mishandling signs in Euler’s recurrence: the sign for both g_k and g'_k is ((-1)^{k-1}), giving the pattern +, +, −, −, +, +, … when terms are ordered by size. A common bug is alternating signs every term rather than every k. • Integer overflow: p(n) grows very fast. Use modular arithmetic or big integers; even 64-bit is insufficient for moderately large n. • Stopping conditions: in the Euler loop, stop when the smallest remaining generalized pentagonal number exceeds n; also guard negative indices by defining p(neg)=0. • Expecting the Hardy–Ramanujan approximation to be exact for small n: it becomes accurate for moderately large n (e.g., n ≥ 50–100); use exact DP for correctness.

Key Formulas

Partition Generating Function

n = 0 \sum \infty p (n) x^{n} = k = 1 \prod \infty (1 - x^{k})^{- 1}

Explanation: Each factor (1 - $x^{k}$ )^{-1} expands to 1 + $x^{k}$ + $x^{2 k}$ + ⋯, allowing unlimited copies of part size k. The coefficient of $x^{n}$ in the product counts all partitions of n.

Euler’s Pentagonal Number Theorem

k = 1 \prod \infty (1 - x^{k}) = m = - \infty \sum \infty (- 1)^{m} x^{\frac{m ( 3 m - 1 )}{2}}

Explanation: The product collapses to a sparse series supported exactly at generalized pentagonal numbers. This identity enables a short alternating-sign recurrence for p(n).

Euler Recurrence for p(n)

p (n) = k = 1 \sum \infty (- 1)^{k - 1} (p (n - g_{k}) + p (n - g_{k}^{'})), g_{k} = \frac{k ( 3 k - 1 )}{2}, g_{k}^{'} = \frac{k ( 3 k + 1 )}{2}

Explanation: To compute p(n), look back at indices offset by generalized pentagonal numbers. Only O( $n$ ) terms are nonzero for each n because $g_{k}$ grows quadratically.

Hardy–Ramanujan Asymptotic

p (n) \sim \frac{1}{4 n 3} exp (π \frac{2 n}{3})

Explanation: This gives an accurate estimate of p(n) for large n. The exponential in $ $n$ $ explains the rapid growth of p(n).

Distinct Parts = Odd Parts

k = 1 \prod \infty (1 + x^{k}) = k = 1 \prod \infty (1 - x^{2 k - 1})^{- 1}

Explanation: The left-hand side generates partitions into distinct parts; the right-hand side generates partitions into odd parts. Equality shows these two counts match for each n.

DP with Largest Part at Most k

p (n, k) = p (n, k - 1) + p (n - k, k), p (0, k) = 1, p (n < 0, k) = 0, p (n, 0) = 0

Explanation: This 2D recurrence counts partitions of n with largest $p a r t \leq k$ . It leads to an O(nk) dynamic program that can compute all p(n) with k up to n.

Count of Pentagonal Terms

K (n) = ⌊ \frac{24 n + 1 + 1}{6} ⌋

Explanation: For a fixed n, only k up to K(n) contribute to the Euler recurrence because $g_{k}$ and g'_k exceed n afterward. This justifies the O( $n$ ) term count.

Complexity Analysis

There are two standard exact algorithms. The unbounded knapsack DP (coin-change style) initializes dp[0]=1 and, for each part size i from 1 to n, updates dp[s]+=dp[s−i] for

s = i

..n. Each of the n coins touches up to n states, yielding O(

n^{2}

) time and O(n) space if we keep a 1D array. This approach naturally extends to constrained partitions (e.g., distinct parts or using only odd parts) by altering the coin set or the loop direction (decreasing s for

\frac{0}{1}

choices). For n around 2e4–1e5 and a single computation, O(

n^{2}

) can be acceptable in practice. Euler’s pentagonal recurrence computes p(0..n) sequentially with p(0)=1. For each n, it sums at offsets given by generalized pentagonal numbers

g_{k}

and g'_k, both with sign (−1)^{k−1}. The number of contributing k is K(n)=Θ(√n), so the total time is \(

\sum_{m = 1}^{n}

Θ(

m

) = Θ(

n^{3/2}

)\). Space usage remains O(n) for storing all p(0..n). In practice, this is significantly faster than O(

n^{2}

) for large n (e.g.,

n \geq 1 e 5

) and is the default choice in competitive programming. If only a single p(n) is needed (not all prefixes), the same Euler recurrence still requires all smaller p(·) values, so asymptotic work is unchanged. Approximating p(n) via Hardy–Ramanujan is O(1) time and space, but it is not exact. For modular computations, all time bounds hold with small constant factors; beware of modulo operations and sign handling costs, which are negligible compared to the arithmetic.

Code Examples

O(n^2) DP (Unbounded Knapsack) to Compute p(n) modulo MOD

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute partition numbers p(0..N) modulo MOD using classic DP.
5 // Time: O(N^2), Space: O(N)
6 
7 int main() {
8     ios::sync_with_stdio(false);
9     cin.tie(nullptr);
10 
11     int N = 1000;                 // change as needed
12     const int MOD = 1'000'000'007; // typical contest modulus
13 
14     vector<int> dp(N + 1, 0);
15     dp[0] = 1; // exactly one way to make sum 0: take nothing (empty partition)
16 
17     // Unbounded knapsack: unlimited copies of each part size i
18     for (int i = 1; i <= N; ++i) {
19         for (int s = i; s <= N; ++s) {
20             dp[s] += dp[s - i];
21             if (dp[s] >= MOD) dp[s] -= MOD;
22         }
23     }
24 
25     // dp[n] now equals p(n) modulo MOD
26     cout << "p(" << N << ") mod MOD = " << dp[N] << "\n";
27 
28     // (Optional) print a few values
29     for (int n = 0; n <= 20; ++n) {
30         cout << "p(" << n << ") = " << dp[n] << "\n";
31     }
32     return 0;
33 }
34

We treat each integer i=1..N as a coin available in unlimited quantity. The 1D DP array dp[s] counts partitions of s. Iterating sums increasing ensures each part size can be reused without introducing order (so compositions are not counted). The base case dp[0]=1 corresponds to the empty partition.

Time: O(n^2)Space: O(n)

Euler’s Pentagonal Recurrence: O(n√n) for all p(0..n) modulo MOD

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute partition numbers p(0..N) using Euler's recurrence.
5 // p(0) = 1; for n >= 1:
6 // p(n) = sum_{k>=1} (-1)^{k-1} ( p(n - gk) + p(n - gk') ),
7 // where gk = k(3k - 1)/2 and gk' = k(3k + 1)/2.
8 // Stop adding when the offset exceeds n. Terms with negative index are zero.
9 // Time: O(N * sqrt(N)), Space: O(N)
10 
11 static inline int addmod(int a, int b, int MOD){ a += b; if(a >= MOD) a -= MOD; return a; }
12 static inline int submod(int a, int b, int MOD){ a -= b; if(a < 0) a += MOD; return a; }
13 
14 int main(){
15     ios::sync_with_stdio(false);
16     cin.tie(nullptr);
17 
18     int N = 100000;               // up to 1e6 is feasible with optimization and fast I/O
19     const int MOD = 1'000'000'007;
20 
21     vector<int> p(N + 1, 0);
22     p[0] = 1;
23 
24     for(int n = 1; n <= N; ++n){
25         long long ans = 0; // we accumulate in signed 64-bit then reduce mod at the end
26         for(long long k = 1;; ++k){
27             long long g1 = k * (3*k - 1) / 2; // k(3k-1)/2
28             if(g1 > n) break;
29             int sign = (k % 2 == 1) ? +1 : -1; // (-1)^{k-1}
30             ans += sign * 1LL * p[n - (int)g1];
31 
32             long long g2 = k * (3*k + 1) / 2; // k(3k+1)/2
33             if(g2 <= n) ans += sign * 1LL * p[n - (int)g2];
34         }
35         // map ans to [0, MOD)
36         long long res = ans % MOD;
37         if(res < 0) res += MOD;
38         p[n] = (int)res;
39     }
40 
41     cout << "p(" << N << ") mod MOD = " << p[N] << "\n";
42 
43     // Sanity check small values
44     for(int n = 0; n <= 20; ++n) cout << "p(" << n << ") = " << p[n] << '\n';
45     return 0;
46 }
47

This implements Euler’s recurrence using generalized pentagonal numbers. For each n, only about O(√n) offsets contribute. The sign is (−1)^{k−1} for both g1 and g2 at the same k, yielding the +, +, −, −, … pattern when terms are sorted by size. The code computes all p(0..N) modulo MOD.

Time: O(n^{3/2})Space: O(n)

Distinct Parts vs Odd Parts: Equality via Two DPs

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Verify Euler's identity: number of partitions into distinct parts equals
5 // number of partitions into odd parts, for all n up to N (mod MOD).
6 
7 static vector<int> partitions_distinct(int N, int MOD){
8     vector<int> dp(N+1, 0);
9     dp[0] = 1;
10     // 0/1 knapsack over parts 1..N (each used at most once)
11     for(int part = 1; part <= N; ++part){
12         for(int s = N; s >= part; --s){
13             dp[s] += dp[s - part];
14             if(dp[s] >= MOD) dp[s] -= MOD;
15         }
16     }
17     return dp;
18 }
19 
20 static vector<int> partitions_odd(int N, int MOD){
21     vector<int> dp(N+1, 0);
22     dp[0] = 1;
23     // Unbounded knapsack over odd parts only
24     for(int part = 1; part <= N; part += 2){
25         for(int s = part; s <= N; ++s){
26             dp[s] += dp[s - part];
27             if(dp[s] >= MOD) dp[s] -= MOD;
28         }
29     }
30     return dp;
31 }
32 
33 int main(){
34     ios::sync_with_stdio(false);
35     cin.tie(nullptr);
36 
37     int N = 2000;                 // demonstration bound
38     const int MOD = 1'000'000'007;
39 
40     auto A = partitions_distinct(N, MOD);
41     auto B = partitions_odd(N, MOD);
42 
43     bool ok = true;
44     for(int n = 0; n <= N; ++n){
45         if(A[n] != B[n]){ ok = false; cerr << "Mismatch at n=" << n << "\n"; break; }
46     }
47 
48     cout << (ok ? "All equal up to N." : "Found mismatch.") << "\n";
49     // Print a few sample values
50     for(int n = 0; n <= 20; ++n){
51         cout << n << ": distinct=" << A[n] << ", odd=" << B[n] << '\n';
52     }
53     return 0;
54 }
55

Two DPs compute: (1) partitions into distinct parts via 0/1 knapsack over parts 1..N; (2) partitions into odd parts via unbounded knapsack over odd parts. The identity $\prod (1+x^k) = \prod (1 - x^{2k-1})^{-1}$ implies equality for each n, which the program verifies modulo MOD.

Time: O(n^2)Space: O(n)

Hardy–Ramanujan Approximation for p(n) (floating-point)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Approximate p(n) using the Hardy–Ramanujan leading term:
5 // p(n) ~ 1/(4 n sqrt(3)) * exp(pi * sqrt(2n/3))
6 // Uses long double for better precision.
7 
8 long double approx_p(long long n){
9     if(n == 0) return 1.0L;
10     const long double pi = acosl(-1.0L);
11     long double nn = (long double)n;
12     long double s = sqrtl( (2.0L*nn)/3.0L );
13     long double val = expl(pi * s) / (4.0L * nn * sqrtl(3.0L));
14     return val;
15 }
16 
17 int main(){
18     ios::sync_with_stdio(false);
19     cin.tie(nullptr);
20 
21     vector<int> test = {10, 50, 100, 200, 500, 1000};
22     cout.setf(std::ios::fixed); cout << setprecision(3);
23     for(int n : test){
24         long double est = approx_p(n);
25         cout << "n=" << n << ": approx p(n) ~ " << (double)est << '\n';
26     }
27     return 0;
28 }
29

Implements the leading-term Hardy–Ramanujan approximation using long double. This is useful for sanity checks and understanding growth. It is not exact, especially for small n; accuracy improves as n increases.

Time: O(1)Space: O(1)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute partition numbers p(0..N) modulo MOD using classic DP.
5	// Time: O(N^2), Space: O(N)
6
7	int main() {
8	ios::sync_with_stdio(false);
9	cin.tie(nullptr);
10
11	int N = 1000; // change as needed
12	const int MOD = 1'000'000'007; // typical contest modulus
13
14	vector<int> dp(N + 1, 0);
15	dp[0] = 1; // exactly one way to make sum 0: take nothing (empty partition)
16
17	// Unbounded knapsack: unlimited copies of each part size i
18	for (int i = 1; i <= N; ++i) {
19	for (int s = i; s <= N; ++s) {
20	dp[s] += dp[s - i];
21	if (dp[s] >= MOD) dp[s] -= MOD;
22	}
23	}
24
25	// dp[n] now equals p(n) modulo MOD
26	cout << "p(" << N << ") mod MOD = " << dp[N] << "\n";
27
28	// (Optional) print a few values
29	for (int n = 0; n <= 20; ++n) {
30	cout << "p(" << n << ") = " << dp[n] << "\n";
31	}
32	return 0;
33	}
34

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute partition numbers p(0..N) using Euler's recurrence.
5	// p(0) = 1; for n >= 1:
6	// p(n) = sum_{k>=1} (-1)^{k-1} ( p(n - gk) + p(n - gk') ),
7	// where gk = k(3k - 1)/2 and gk' = k(3k + 1)/2.
8	// Stop adding when the offset exceeds n. Terms with negative index are zero.
9	// Time: O(N * sqrt(N)), Space: O(N)
10
11	static inline int addmod(int a, int b, int MOD){ a += b; if(a >= MOD) a -= MOD; return a; }
12	static inline int submod(int a, int b, int MOD){ a -= b; if(a < 0) a += MOD; return a; }
13
14	int main(){
15	ios::sync_with_stdio(false);
16	cin.tie(nullptr);
17
18	int N = 100000; // up to 1e6 is feasible with optimization and fast I/O
19	const int MOD = 1'000'000'007;
20
21	vector<int> p(N + 1, 0);
22	p[0] = 1;
23
24	for(int n = 1; n <= N; ++n){
25	long long ans = 0; // we accumulate in signed 64-bit then reduce mod at the end
26	for(long long k = 1;; ++k){
27	long long g1 = k * (3*k - 1) / 2; // k(3k-1)/2
28	if(g1 > n) break;
29	int sign = (k % 2 == 1) ? +1 : -1; // (-1)^{k-1}
30	ans += sign * 1LL * p[n - (int)g1];
31
32	long long g2 = k * (3*k + 1) / 2; // k(3k+1)/2
33	if(g2 <= n) ans += sign * 1LL * p[n - (int)g2];
34	}
35	// map ans to [0, MOD)
36	long long res = ans % MOD;
37	if(res < 0) res += MOD;
38	p[n] = (int)res;
39	}
40
41	cout << "p(" << N << ") mod MOD = " << p[N] << "\n";
42
43	// Sanity check small values
44	for(int n = 0; n <= 20; ++n) cout << "p(" << n << ") = " << p[n] << '\n';
45	return 0;
46	}
47

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Verify Euler's identity: number of partitions into distinct parts equals
5	// number of partitions into odd parts, for all n up to N (mod MOD).
6
7	static vector<int> partitions_distinct(int N, int MOD){
8	vector<int> dp(N+1, 0);
9	dp[0] = 1;
10	// 0/1 knapsack over parts 1..N (each used at most once)
11	for(int part = 1; part <= N; ++part){
12	for(int s = N; s >= part; --s){
13	dp[s] += dp[s - part];
14	if(dp[s] >= MOD) dp[s] -= MOD;
15	}
16	}
17	return dp;
18	}
19
20	static vector<int> partitions_odd(int N, int MOD){
21	vector<int> dp(N+1, 0);
22	dp[0] = 1;
23	// Unbounded knapsack over odd parts only
24	for(int part = 1; part <= N; part += 2){
25	for(int s = part; s <= N; ++s){
26	dp[s] += dp[s - part];
27	if(dp[s] >= MOD) dp[s] -= MOD;
28	}
29	}
30	return dp;
31	}
32
33	int main(){
34	ios::sync_with_stdio(false);
35	cin.tie(nullptr);
36
37	int N = 2000; // demonstration bound
38	const int MOD = 1'000'000'007;
39
40	auto A = partitions_distinct(N, MOD);
41	auto B = partitions_odd(N, MOD);
42
43	bool ok = true;
44	for(int n = 0; n <= N; ++n){
45	if(A[n] != B[n]){ ok = false; cerr << "Mismatch at n=" << n << "\n"; break; }
46	}
47
48	cout << (ok ? "All equal up to N." : "Found mismatch.") << "\n";
49	// Print a few sample values
50	for(int n = 0; n <= 20; ++n){
51	cout << n << ": distinct=" << A[n] << ", odd=" << B[n] << '\n';
52	}
53	return 0;
54	}
55

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Approximate p(n) using the Hardy–Ramanujan leading term:
5	// p(n) ~ 1/(4 n sqrt(3)) * exp(pi * sqrt(2n/3))
6	// Uses long double for better precision.
7
8	long double approx_p(long long n){
9	if(n == 0) return 1.0L;
10	const long double pi = acosl(-1.0L);
11	long double nn = (long double)n;
12	long double s = sqrtl( (2.0L*nn)/3.0L );
13	long double val = expl(pi * s) / (4.0L * nn * sqrtl(3.0L));
14	return val;
15	}
16
17	int main(){
18	ios::sync_with_stdio(false);
19	cin.tie(nullptr);
20
21	vector<int> test = {10, 50, 100, 200, 500, 1000};
22	cout.setf(std::ios::fixed); cout << setprecision(3);
23	for(int n : test){
24	long double est = approx_p(n);
25	cout << "n=" << n << ": approx p(n) ~ " << (double)est << '\n';
26	}
27	return 0;
28	}
29