Integer Partitions

A partition of a positive integer n is a way of writing it as a sum of positive integers, order ignored. This tool computes p(n) — the number of unrestricted partitions — using Euler's pentagonal-number recurrence (exact big-integer arithmetic, fast for large n), q(n) — the number of partitions into distinct parts — by a 0/1 subset-sum count, and lists the actual partitions for small n. For example p(10) = 42, p(100) = 190569292, q(10) = 10. Runs locally in your browser.

Input

n =

Counts

—

Partitions

—

p(n) counts unordered sums of positive integers equal to n (p(0) = 1 by convention). It is computed from Euler's recurrence p(n) = Σₖ (−1)ᵏ⁻¹ [p(n − k(3k−1)/2) + p(n − k(3k+1)/2)] over the generalized pentagonal numbers 1, 2, 5, 7, 12, 15, … — an O(n√n) algorithm that stays exact for large n. q(n) counts partitions into distinct parts (each part used at most once), computed by a 0/1 subset-sum dynamic program over {1,…,n}; it is exact but O(n²), so it is capped for very large n. The listing is generated recursively and capped at a few thousand rows for readability. Pairs with the Combinatorics, Fibonacci, and Collatz tools. Everything runs locally — nothing leaves your browser.