Efficient implementation of the Hardy-Ramanujan-Rademacher formula

Abstract

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.

updated version containing an unconditional complexity proof; accepted for publication in LMS Journal of Computation and Mathematics

Cited by in corpus (9)

• Class polynomials for nonholomorphic modular functions
• Complexity problems in enumerative combinatorics
• Congruences satisfied by eta-quotients
• Efficient computation of the overpartition function and applications
• What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I
• Will the real Hardy-Ramanujan formula please stand up?
• Approximation of the Partition Number After Hardy and Ramanujan: An Application of Data Fitting Method in Combinatorics
• Computing isolated coefficients of the $j$-function
• Explicit families of congruences for the overpartition function