×

Efficient implementation of the Hardy-Ramanujan-Rademacher formula. (English) Zbl 1344.11089

Summary: 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. Supplementary materials are available with this article.

MSC:

11Y55 Calculation of integer sequences
11-04 Software, source code, etc. for problems pertaining to number theory
11P81 Elementary theory of partitions
11P83 Partitions; congruences and congruential restrictions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Tonelli, Göttinger Nachrichten pp 344– (1891)
[2] DOI: 10.2307/2324301 · Zbl 0796.11008 · doi:10.2307/2324301
[3] DOI: 10.1112/plms/s2-43.4.241 · Zbl 0017.05503 · doi:10.1112/plms/s2-43.4.241
[4] DOI: 10.1016/j.jnt.2011.12.015 · Zbl 1300.11008 · doi:10.1016/j.jnt.2011.12.015
[5] DOI: 10.1137/1.9780898718027 · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[6] DOI: 10.1017/S1446788712000146 · Zbl 1251.11088 · doi:10.1017/S1446788712000146
[7] DOI: 10.1112/plms/s2-17.1.75 · JFM 46.0198.04 · doi:10.1112/plms/s2-17.1.75
[8] Crandall, Prime numbers: a computational perspective pp 99– (2005)
[9] DOI: 10.1090/S0002-9939-1970-0265308-2 · doi:10.1090/S0002-9939-1970-0265308-2
[10] Cipolla, Napoli Rend. 9 pp 153– (1903)
[11] DOI: 10.1090/S0025-5718-07-01966-7 · Zbl 1113.11057 · doi:10.1090/S0025-5718-07-01966-7
[12] Brent, Modern computer arithmetic (2011)
[13] Erdos, Mat. Lapok 12 pp 10– (1961)
[14] Borwein, Experimental and computational mathematics: selected writings (2010) · Zbl 1225.01096
[15] Borwein, Mathematics by experiment: plausible reasoning in the 21st century (2003) · Zbl 1163.00002
[16] Apostol, Modular functions and Dirichlet series in number theory (1997)
[17] DOI: 10.2307/1969420 · Zbl 0046.04006 · doi:10.2307/1969420
[18] DOI: 10.2307/121118 · Zbl 0984.11050 · doi:10.2307/121118
[19] Odlyzko, Handbook of combinatorics 2 pp 1063– (1995)
[20] DOI: 10.1112/jlms/s1-12.2.171 · Zbl 0017.05601 · doi:10.1112/jlms/s1-12.2.171
[21] DOI: 10.1112/jlms/s1-11.2.114 · Zbl 0014.34204 · doi:10.1112/jlms/s1-11.2.114
[22] DOI: 10.1090/S0002-9947-1938-1501943-5 · JFM 64.0120.03 · doi:10.1090/S0002-9947-1938-1501943-5
[23] Knuth, Fascicle 3: generating all combinations and partitions (2005)
[24] Knuth, Acta Arith. 33 pp 297– (1977)
[25] Whiteman, Pacific J. Math. 6 pp 159– (1956) · Zbl 0071.04004 · doi:10.2140/pjm.1956.6.159
[26] DOI: 10.1023/A:1011493128408 · Zbl 0986.11071 · doi:10.1023/A:1011493128408
[27] DOI: 10.2307/2371532 · Zbl 0025.02802 · doi:10.2307/2371532
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.