Introduction

Take a whole number — say 4 — and ask a child's question: in how many ways can you write it as a sum of positive whole numbers, if order doesn't matter? You get 5: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. That count is the value of the partition function, written p(4) = 5.

The rule could not be gentler, yet the answer races away. p(10) is already 42. p(100) is 190,569,292. p(1000) is a 32-digit number — roughly 2.4×10312.4 \times 10^{31}. Listing the partitions one by one is hopeless almost immediately.

What makes p(n) one of the most beautiful objects in mathematics is that this runaway growth is not random. It is captured — astonishingly well — by a single formula discovered in 1918.

Count the Partitions

Pick a number n with the slider. The demo computes the exact value of p(n) using Euler's recurrence, then shows the Hardy–Ramanujan estimate beside it — watch how closely the simple formula tracks the true count, even as both explode.

<p class="hint">In how many ways can you write <b>n</b> as a sum of positive integers, ignoring order? That count is <b>p(n)</b>. Slide n and watch the exact count explode while the Hardy&ndash;Ramanujan estimate tracks it.</p>
<div class="row">
  <label for="n">n = <b id="nlabel">10</b></label>
  <input id="n" type="range" min="1" max="120" value="10" />
</div>
<div class="grid">
  <div class="stat"><div class="k">exact p(n)</div><div class="v" id="exact">42</div></div>
  <div class="stat"><div class="k">Hardy&ndash;Ramanujan estimate</div><div class="v" id="approx">48.1</div></div>
  <div class="stat"><div class="k">relative error</div><div class="v" id="err">14.4%</div></div>
</div>
<div class="btns">
  <button id="list" type="button">List the partitions of n</button>
  <button id="reset" type="button" class="ghost">Reset to 10</button>
</div>
<div class="status" id="status"></div>
<div class="parts" id="parts"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .8rem; margin: .4rem 0 1rem; }
.row label { font: 600 15px system-ui, sans-serif; white-space: nowrap; }
.row input[type=range] { flex: 1; accent-color: #1d3557; }
.grid { display: grid; grid-template-columns: repeat(3, 1fr); gap: .6rem; margin-bottom: 1rem; }
.stat { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .7rem; }
.stat .k { font-size: .72rem; text-transform: uppercase; letter-spacing: .03em; color: #5a7088; }
.stat .v { font: 700 19px ui-monospace, monospace; color: #1d3557; margin-top: .25rem; word-break: break-all; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; margin: .7rem 0 .2rem; color: #5a7088; min-height: 1.2em; }
.parts { display: flex; flex-wrap: wrap; gap: .35rem; }
.part { background: #fff; border: 1px solid #cdd9e3; border-radius: 6px;
        padding: .2rem .5rem; font: 600 13px ui-monospace, monospace; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The partition function p(n): the number of ways to write n as a sum of
// p(4)=5: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
// EXACT count: Euler's pentagonal-number recurrence
//   p(n) = sum_k (-1)^(k-1) [ p(n - k(3k-1)/2) + p(n - k(3k+1)/2) ]
// which fills a table in polynomial time. We use BigInt so big p(n) stays exact.
const MAX = 120;
const P = [1n]; // p(0) = 1
for (let n = 1; n <= MAX; n++) {
  let sum = 0n;
  for (let k = 1; ; k++) {
    const g1 = (k * (3 * k - 1)) / 2;   // generalized pentagonal numbers
    const g2 = (k * (3 * k + 1)) / 2;
    if (g1 > n && g2 > n) break;
    const sign = (k % 2 === 1) ? 1n : -1n;
    if (g1 <= n) sum += sign * P[n - g1];
    if (g2 <= n) sum += sign * P[n - g2];
  }
  P[n] = sum;
}

// Hardy-Ramanujan (1918) asymptotic: p(n) ~ exp(pi*sqrt(2n/3)) / (4 n sqrt(3)).
function hr(n) {
  if (n === 0) return 1;
  return Math.exp(Math.PI * Math.sqrt(2 * n / 3)) / (4 * n * Math.sqrt(3));
}

function fmt(big) { return big.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ','); }
function fmtApprox(x) {
  if (x < 1e6) return x.toLocaleString(undefined, { maximumFractionDigits: 1 });
  return x.toExponential(3);
}

const slider = document.getElementById('n');
const nlabel = document.getElementById('nlabel');
const exactEl = document.getElementById('exact');
const approxEl = document.getElementById('approx');
const errEl = document.getElementById('err');
const status = document.getElementById('status');
const parts = document.getElementById('parts');

function update() {
  const n = +slider.value;
  nlabel.textContent = n;
  const exact = P[n];
  const approx = hr(n);
  exactEl.textContent = fmt(exact);
  approxEl.textContent = fmtApprox(approx);
  // relative error of the estimate vs the exact count
  const rel = Math.abs(approx - Number(exact)) / Number(exact) * 100;
  errEl.textContent = rel.toFixed(rel < 1 ? 2 : 1) + '%';
  parts.innerHTML = '';
  status.textContent = '';
}

// List actual partitions (only sane for small n).
function listPartitions(n) {
  const out = [];
  (function go(rem, max, acc) {
    if (rem === 0) { out.push(acc.join('+')); return; }
    for (let i = Math.min(rem, max); i >= 1; i--) go(rem - i, i, [...acc, i]);
  })(n, n, []);
  return out;
}

document.getElementById('list').addEventListener('click', () => {
  const n = +slider.value;
  parts.innerHTML = '';
  if (n > 14) {
    status.textContent = i18nFmt('p(%n%) = %fmt% partitions — far too many to list. Try n ≤ 14.', { n: n, fmt: fmt(P[n]) });
    return;
  }
  const list = listPartitions(n);
  status.textContent = i18nFmt('All %length% partitions of %n% (and p(%n%) = %fmt%):', { length: list.length, n: n, fmt: fmt(P[n]) });
  for (const s of list) {
    const d = document.createElement('span');
    d.className = 'part'; d.textContent = s; parts.appendChild(d);
  }
  console.log(i18nFmt('p(%n%) =', { n: n }), P[n].toString(), '| listed', list.length, 'partitions');
});

document.getElementById('reset').addEventListener('click', () => {
  slider.value = 10; update();
});
slider.addEventListener('input', update);
update();
Result
Console

Notice two things. First, the growth: each step up in n multiplies the count by more and more. Second, the approximation: the rough formula e^(π√(2n/3)) / (4n√3) is never exact, but its relative error shrinks steadily as n grows — from about 14% at n = 10 down toward a few percent by n in the hundreds, and on toward zero. Counting cleverly with a recurrence is fast; the formula explains why the numbers look the way they do.

The Real Complexity

So how do you handle a number that explodes this fast?

  • Listing is hopeless. The number of partitions itself is what we're counting, so enumerating them takes time proportional to the (astronomical) answer.
  • A recurrence makes it fast. Euler's pentagonal-number recurrence computes p(n) from earlier values, so the exact count is reachable in polynomial time — that's how the demo fills its table.
  • Hardy and Ramanujan (1918) found the headline result: an asymptotic formula, p(n) ~ e^(π√(2n/3)) / (4n√3). It is never exactly right, but the ratio to the true value tends to 1 as n grows — a stunning bridge from a discrete count to the constants π\pi and ee.
  • Rademacher (1937) went further, turning the asymptotic into an exact convergent series: round its first few terms and you recover p(n) on the nose.

That is the punchline: this is a solved problem, not an open one. There is no Millennium mystery here and nothing undecidable — just one of the most elegant results in analytic number theory, where the wild growth of a simple count is pinned down by a clean formula. It is the same spirit as asking how hard it is to compute π: the object looks intractable, but the right idea tames it.

Where It Matters

"Split a total into unordered parts" turns out to be a shape that appears all over science and mathematics:

  • Statistical physics: counting the ways energy quanta can be distributed among modes is literally a partition count — it underlies the thermodynamics of ideal systems.
  • Representation theory: partitions of n label the irreducible representations of the symmetric group and index Young diagrams, a cornerstone of algebra.
  • Combinatorics and generating functions: Euler's product formula for partitions is the gateway example for the whole theory of generating functions.
  • Analysis of algorithms: the same growth governs how many ways a quantity can be broken up, which shows up in counting problems related to subset sum and other ways of decomposing a target.

Learn the partition function and you've met a recurring melody — the moment a problem asks "how many ways to break this total apart," p(n) and its relatives are nearby.

Conclusion

The partition function hides a quiet marvel: a question simple enough for a child — how many ways can you add up to n? — produces numbers that outrun any list, and yet Hardy and Ramanujan showed in 1918 that those numbers obey a clean formula built from π\pi and ee. Rademacher later made it exact.

So the next time a count seems to explode beyond reach, remember p(n). Explosive growth is not the same as chaos. Sometimes the wildest-looking sequence in arithmetic turns out to be following an elegant rule — and the real adventure is finding it. For another count that looks impossible until the right idea arrives, see how hard it is to compute π.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/partition-function/Content licensed under CC BY-NC 4.0.