Computing p(n)

Values with $n < 128$ are read from a table, values with $n < 417$ (where $p(n) < 2^{64}$, on 64-bit machines) are computed with Euler's pentagonal recurrence in single words, and larger values with mp_real_partitions_hrr. The number of threads set with flint_set_num_threads is used from about $n = 10^8$. partitions_fmpz_fmpz accepts $n < 2^{128}$ and throws for larger $n$; the result must also fit in an fmpz, which limits $n$ to about $1.4 \cdot 10^{21}$ on 64-bit machines. Beyond, use mp_real_partitions_hrr directly.

partitions_fmpz_ui and partitions_fmpz_fmpz compute one value of the partition function exactly, in time roughly proportional to the size of the result, $O(n^{1/2 + o(1)})$. They are the functions to use for a single $p(n)$ with $n$ beyond a few thousand. For all values up to $n$, arith_number_of_partitions_vec (power series inversion, $O(n^{3/2 + o(1)})$ for the whole vector) is cheaper than $n$ separate calls; for $p(n)$ modulo a word-size integer and all $n$ up to a bound, arith_number_of_partitions_nmod_vec.

Methods#

The formula is evaluated as a ball whose radius covers the rounding errors of every term and Rademacher's bound for the truncation error; the function returns the unique integer in the ball (Integers from balls). It never returns an incorrect value: if the ball contained no integer or several, it would throw, which is not expected to happen. The terms are computed in parallel from about $n = 10^8$ when threads are enabled with flint_set_num_threads.

The limits are those of the data types: partitions_fmpz_fmpz throws for $n \ge 2^{128}$, and the result must fit in an fmpz, whose size is limited to about $2^{37}$ bits on 64-bit machines, which holds up to $n \approx 1.4 \cdot 10^{21}$. The memory needed is a small multiple of the size of the result, which is about $0.46 \sqrt n$ bytes.

Example#

The program prints $p(100)$ and $p(1000)$, computes $p(10^9)$ and compares it with the leading term of the series. The relative difference is of the order of $e^{-t/2}$, where $t = \pi\sqrt{24 n - 1}/6$, which for $n = 10^9$ is about $10^{-17600}$; at 128 bits the ratio is 1 up to the rounding error.

#include <flint/flint.h>
#include <flint/fmpz.h>
#include <flint/arb.h>
#include <flint/partitions.h>

int main(void)
{
    fmpz_t p, n;
    arb_t lead, x;

    fmpz_init(p);
    fmpz_init(n);
    arb_init(lead);
    arb_init(x);

    partitions_fmpz_ui(p, 100);
    flint_printf("p(100) = ");
    fmpz_print(p);
    partitions_fmpz_ui(p, 1000);
    flint_printf("\np(1000) = ");
    fmpz_print(p);
    flint_printf("\n");

    fmpz_set_ui(n, 1000000000);
    partitions_fmpz_fmpz(p, n, 0);
    flint_printf("p(10^9) has %wu bits\n", fmpz_bits(p));

    partitions_leading_fmpz(lead, n, 128);
    arb_set_fmpz(x, p);
    arb_div(x, x, lead, 128);
    flint_printf("p(10^9) / leading term = ");
    arb_printn(x, 25, 0);
    flint_printf("\n");

    fmpz_clear(p);
    fmpz_clear(n);
    arb_clear(lead);
    arb_clear(x);
    return 0;
}

p(100) = 190569292
p(1000) = 24061467864032622473692149727991
p(10^9) has 116993 bits
p(10^9) / leading term = [1.000000000000000000000000 +/- 9.48e-38]