Integer Partition Calculator: How to Count Every Way to Sum to n
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
An integer partition calculator answers one question: how many ways can a number be written as a sum of positive whole numbers? For 100, the answer is 190,569,292. Not a hundred, not a few thousand — a hundred and ninety million distinct sums, from the single term 100 down to a hundred ones, and every staircase in between.
That number is the reason the topic exists. Nothing about 100 hints at 1.9 × 10⁸, there is no formula that produces it in one line, and the naive approach — write them all down — is dead on arrival. What follows is the machinery that gets you there anyway: the ordering rule that makes partitions so much smaller than they look, Euler’s four-term shortcut, the diagram flip that turns two questions into one, the theorem nobody expects to be true, and the three divisibility rules Ramanujan found by staring at a table.
Order Is the Only Thing Separating 190 Million From 6 × 10²⁹
Start with the distinction that trips up more people than any other piece of this topic. A composition of n counts ordered sums: 3 + 1 and 1 + 3 are two different compositions of 4. A partition counts unordered sums, so 3 + 1 and 1 + 3 are the same thing written twice. The gap between those two counts is not a rounding difference.
| n | Compositions (order matters) | Partitions p(n) (order ignored) | Ratio |
|---|---|---|---|
| 4 | 8 | 5 | 1.6 |
| 8 | 128 | 22 | 5.8 |
| 20 | 524,288 | 627 | 836 |
| 100 | 6.34 × 10²⁹ | 190,569,292 | 3.3 × 10²¹ |
Compositions have a one-line formula: 2ⁿ⁻¹, because you walk along a row of n ones and decide independently, at each of the n − 1 gaps, whether to place a plus sign or fuse the neighbours. Partitions have no such formula. Killing the order destroys exactly the structure that makes the counting easy — which is why combinatorics problems that look almost identical can be an afternoon apart in difficulty.
Two other collisions are worth clearing up while we’re here. Partitioning the number 5 gives 7 answers; partitioning a set of 5 labelled objects gives 52, the fifth Bell number. And ordering all 5 objects gives 120, a plain factorial. Same input, three completely different questions, and the word “partition” is doing double duty in two of them.
Euler’s Shortcut: How an Integer Partition Calculator Gets p(10) in Four Terms
Here is the calculation the tool above runs. Euler proved that p(n) can be reached from earlier partition numbers using offsets drawn from the generalised pentagonal numbers — 1, 2, 5, 7, 12, 15, 22, 26, 35, 40 — with signs that alternate in pairs: plus, plus, minus, minus, plus, plus.
p(n) = p(n−1) + p(n−2) − p(n−5) − p(n−7) + p(n−12) + p(n−15) − …
Run it at n = 10, using p(0…9) = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30:
p(10) = p(9) + p(8) − p(5) − p(3) = 30 + 22 − 7 − 3 = 42
Four terms. The next offset, 12, is already larger than 10, so the sum stops there. That is the whole algorithm, and it explains why a partition calculator can hit n = 1000 without breaking a sweat: the number of terms grows like 2√(2n/3), so p(1000) — a 32-digit number — needs fewer than 60 additions once the earlier values are in hand.
Compare that with the alternatives. The obvious dynamic program fills an n × n grid; brute-force enumeration is worse than hopeless.
| Method | Work for p(1000) | Gives you |
|---|---|---|
| Enumerate every partition | 2.4 × 10³¹ steps | The actual sums — and never finishes |
| Knapsack DP over parts 1…n | ~500,000 additions | p(n) plus every restricted variant |
| Pentagonal recurrence | ~33,000 additions | p(n) only, exactly |
| Hardy–Ramanujan formula | One exponential | An estimate, 1.4% high at n = 1000 |
The knapsack row is slower but far more flexible — it is what you want the moment somebody adds a rule like “no part above 4”, because the pentagonal recurrence handles unrestricted partitions and nothing else.
Flip the Dots and Two Different Questions Become One
Draw a partition as rows of dots, longest row on top. That picture is a Ferrers diagram, and 3 + 2 + 2 becomes three rows of 3, 2 and 2 dots. Now read the same picture down the columns instead of across the rows: the columns have 3, 3 and 1 dots, which is the partition 3 + 3 + 1. That new partition is the conjugate, and reflecting twice returns you to where you started.
The consequence is a genuinely useful identity. Reflection swaps “number of parts” with “size of largest part”, so those two counts must be equal:
partitions of n into exactly k parts = partitions of n with largest part exactly k
Check it at n = 7, k = 3. Exactly three parts: 5+1+1, 4+2+1, 3+3+1, 3+2+2 — four of them. Largest part exactly 3: 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1 — also four. The two lists are not the same sums, and only two entries appear in both, but the counts match because conjugation pairs them up one to one.
This is the identity that makes the “exactly k parts” field above worth having. It also drives the recurrence p(n,k) = p(n−1,k−1) + p(n−k,k): either the partition contains a 1, which you delete to leave k − 1 parts summing to n − 1, or every part is at least 2, so you shave one off each of the k parts. Every partition falls into exactly one of those cases, which is what makes the sum a clean split rather than an over-count.
Why Odd Parts and Distinct Parts Always Tie
Euler’s other partition theorem sounds like a coincidence and isn’t: the number of partitions of n into distinct parts always equals the number into odd parts. Here is n = 8 in full, with 6 on each side.
| Distinct parts (6) | Odd parts (6) |
|---|---|
| 8 | 7 + 1 |
| 7 + 1 | 5 + 3 |
| 6 + 2 | 5 + 1 + 1 + 1 |
| 5 + 3 | 3 + 3 + 1 + 1 |
| 5 + 2 + 1 | 3 + 1 + 1 + 1 + 1 + 1 |
| 4 + 3 + 1 | 1 × 8 |
Six and six. Try 20 and you get 64 and 64; try 50 and you get 3,658 and 3,658. The proof is a conversion you can do by hand. Take any partition into odd parts and write each repeated part as a power of two times an odd number — six 3s is 3 × 6 = 3 × (4 + 2), so it becomes 12 + 6. Every piece that comes out is distinct, and the process reverses uniquely by splitting each distinct part into its odd core repeated 2ᵃ times.
There is a third member of this family that the calculator reports too. Partitions into distinct odd parts are equal in number to the self-conjugate partitions — the ones whose Ferrers diagram is symmetric about its diagonal. At n = 8 both counts are 2. The distinct odd sums are 7 + 1 and 5 + 3; the symmetric diagrams are 4 + 2 + 1 + 1 and 3 + 3 + 2. Different sums, matched one to one by turning each odd part 2a + 1 into an L-shaped hook with arm a and leg a. Select 3 + 3 + 2 in the listing above and its conjugate panel comes back identical.
Three Divisibility Rules Found in a Table of Numbers
Ramanujan was reading a printed table of p(n) when he noticed something that had no business being there. Take every fifth value starting at n = 4 — p(4) = 5, p(9) = 30, p(14) = 135, p(19) = 490, p(24) = 1575 — and every one is a multiple of 5. Not approximately. Exactly, for all of them, forever.
p(5m + 4) ≡ 0 (mod 5)
p(7m + 5) ≡ 0 (mod 7)
p(11m + 6) ≡ 0 (mod 11)
Worth pausing on how strange this is. p(n) is defined by a counting problem with no arithmetic structure in sight, yet its residue mod 5 is decided entirely by n mod 5. Put 49 into the calculator: 49 = 5 × 9 + 4, so before anything is computed you know p(49) is divisible by 5. It comes out as 173,525, and 173,525 = 5 × 34,705.
The natural next guess — that 13 has a rule too — is wrong, and that is the useful part of the story. There is no residue r for which p(13m + r) is always divisible by 13. The pattern stops at 11, and the reason involves modular forms rather than anything you can see in the table. If you go hunting for a mod-13 analogue, the congruence panel above will show you the misses directly: p(6) ≡ 11, p(19) ≡ 9, p(32) ≡ 3, all mod 13, with no pattern to them at all.
When to Stop Counting and Start Estimating
Hardy and Ramanujan gave the asymptotic that made partition theory analytic, and it is simple enough to evaluate on a phone:
p(n) ≈ exp(π √(2n/3)) / (4n√3)
It is always an overestimate, and it converges slowly. Slowly enough that treating it as an answer rather than a scale is a real mistake.
| n | Exact p(n) | Hardy–Ramanujan | Error |
|---|---|---|---|
| 10 | 42 | 48.1 | +14.53% |
| 50 | 204,226 | 217,590 | +6.54% |
| 100 | 190,569,292 | 199,280,893 | +4.57% |
| 500 | 2.30 × 10²¹ | 2.35 × 10²¹ | +2.01% |
| 1000 | 2.41 × 10³¹ | 2.44 × 10³¹ | +1.42% |
The error drops roughly like 1/√n, so getting to 0.1% accuracy needs n in the hundreds of thousands. Practical rule: use the formula when you want to know whether an answer has 9 digits or 30, and use the exact recurrence whenever the digits themselves matter. Rademacher later turned the asymptotic into a convergent series that nails p(n) exactly, but it is heavy machinery — for anything under n = 10⁶ the pentagonal recurrence wins on both speed and simplicity.
One more number worth carrying: consecutive partition values grow by a shrinking factor. p(10) is 1.40 times p(9), p(100) is 1.13 times p(99), and by n = 1000 the step is down to 1.04. The running sums grow explosively, but the growth rate is quietly decaying the whole time — a signature of sub-exponential growth like e^√n rather than the eⁿ that most counting sequences show.
Three Problems That Look Like Partitions and Aren’t
Most of the wrong answers in this area come from applying p(n) to a question that only resembles a partition problem. These are the three that come up most.
Coin change with a fixed denomination list. “How many ways can I make 12 from 1s, 2s and 4s?” is a partition problem with a restricted part set, and the answer is 16 — not p(12) = 77, and not the 34 you get from capping parts at 4, because that cap quietly readmits the 3s. Set the largest-part field only when every value up to the cap is genuinely allowed; for an arbitrary denomination list you need a knapsack over that exact set.
Distributing labelled items. Handing out 10 distinct books to identical boxes is a Stirling-number problem; handing out 10 identical marbles to identical boxes is a partition problem. The word that decides it is never in the formula — it is in whether swapping two items produces a new arrangement. If the items have names, p(n) is the wrong tool and combinations and permutations usually are too.
Bin packing and scheduling. Splitting a workload of 100 units across machines looks like partitioning 100, but real versions carry a bin count, capacity limits and an objective to minimise. Partition counting says how many splits exist; it says nothing about which one is good, and the optimisation version is NP-hard while the counting version runs in milliseconds.
A final habit worth building: sanity-check any partition answer against a neighbour. p(n) is strictly increasing from n = 1 onward and grows by less than 50% per step past n = 10, so a result that doubles between consecutive n, or dips, is a bug rather than a surprise. The same check catches most off-by-one errors in hand-rolled DP code, including the classic one where the sequence starts at p(1) = 1 instead of p(0) = 1 and every later value silently shifts.
For the raw values themselves, OEIS sequence A000041 lists p(n) far past anything you will need, and the partition function article on Wikipedia carries the full statements of the Rademacher series and the congruence proofs.
