Author: Fredrik Johansson
Published in LMS Journal of Computation and Mathematics, Volume 15, 2012, pp. 341-359. DOI=10.1112/S1461157012001088.
arXiv preprint: http://arxiv.org/abs/1205.5991, published May 27, 2012; revised July 6, 2012.
We describe how the Hardy-Ramanujan-Rademacher formula can be implemented to allow the partition function $p(n)$ to be computed with softly optimal complexity $O(n^{1/2+o(1)})$ and very little overhead. A new implementation based on these techniques achieves speedups in excess of a factor 500 over previously published software and has been used by the author to calculate $p(10^{19})$, an exponent twice as large as in previously reported computations. We also investigate performance for multi-evaluation of $p(n)$, where our implementation of the Hardy-Ramanujan-Rademacher formula becomes superior to power series methods on far denser sets of indices than previous implementations. As an application, we determine over 22 billion new congruences for the partition function, extending Weaver's tabulation of 76,065 congruences.
David Broadhurst has pointed out (private communication, August 1, 2013) that the formula for the number of partitions into odd (or distinct) parts given at the end of the paper is incorrect: the exponential sum $A_k(n)$ appearing in this expansion is different from the $A_k(n)$ that appears in the Hardy-Ramanujan-Rademacher formula. The factorization of Selberg and Whiteman can therefore not be used, so it is not clear whether equally fast evaluation of the number of partitions into odd parts is possible.
Two typos reported by Hugo M. Spinelli: equation (2.6) says $\lambda = 0$ instead of the correct $\lambda = 1$, and in Algorithm 2, one must set $s \gets -s$ when $k_1 = 4$.
The implementation is available as part of the FLINT library. Version 5.11 and later of Sage now uses this implementation by default:
sage: %time p = number_of_partitions(10^12); CPU times: user 13.77 s, sys: 0.10 s, total: 13.87 s Wall time: 13.87 s sage: p % 10^10 6867626906
A newer implementation is available as part of the Arb library. This implementation is provably correct (by use of ball arithmetic) and slightly faster for huge $n$.
Tables of congruences are available for download: partdata.zip. The files list $(\ell, \varepsilon)$ for all tuples $(m, \ell, \varepsilon)$ with $\ell < 10^6$.
The huge integers $p(10^{17})$ (0.35 billion digits), $p(10^{18})$ (1.1 billion digits) and $p(10^{19})$ (3.5 billion digits) can be provided upon request.
Last updated April 27, 2019. Contact: fredrik.johansson@gmail.com.
Back to fredrikj.net