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]