partitions.h

This module computes the integer partition function p(n), the number of ways of writing n as a sum of positive integers without regard to order: p(4) = 5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1). Small values come from a table and Euler's pentagonal recurrence; large values from the Hardy–Ramanujan–Rademacher formula, a convergent series whose leading term is about e^{\pi \sqrt{2n/3}}/(4\sqrt 3\, n), so that p(n) has about 3.7 \sqrt n bits. The implementation [Joh2012] evaluates a truncation of the series in ball arithmetic with per-term precision, factors the exponential sums symbolically, and adds Rademacher's bound for the remainder, so the result is proved correct; p(10^9), a number of 117 thousand bits, takes a few hundredths of a second.

The evaluation itself is done by mp_real_partitions_hrr in mp_real, which uses hardware double-based balls (dfloat) for the many low-precision terms and several threads for large n. For all values p(0), \ldots, p(n-1) at once, use arith_number_of_partitions_vec, and for approximations arb_partitions_fmpz. See Computing p(n) for usage and Computing the partition function for the mathematics.