The Partition Function

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

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">{{hint}}</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">{{lbl_exact}}</div><div class="v" id="exact">42</div></div>
  <div class="stat"><div class="k">{{lbl_hr}}</div><div class="v" id="approx">48.1</div></div>
  <div class="stat"><div class="k">{{lbl_err}}</div><div class="v" id="err">14.4%</div></div>
</div>
<div class="btns">
  <button id="list" type="button">{{btn_list}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</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; }

// Code not found

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.

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 $e$.
• 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.

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

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 $e$. 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 π.