Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T21:33:20.031Z Has data issue: false hasContentIssue false

Efficient implementation of the Hardy–Ramanujan–Rademacher formula

Published online by Cambridge University Press:  01 October 2012

Fredrik Johansson*
Affiliation:
Research Institute for Symbolic Computation, Johannes Kepler University, Altenberger Strasse 69, 4040 Linz, Austria (email: fredrik.johansson@risc.jku.at)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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(n1/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(1019), 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. Supplementary materials are available with this article.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2012