Johansson, Fredrik Efficient implementation of the Hardy-Ramanujan-Rademacher formula. (English) Zbl 1344.11089 LMS J. Comput. Math. 15, 341-359 (2012). 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. Cited in 2 ReviewsCited in 15 Documents 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 Keywords:partition function; multi-evaluation of partition function Software:MPIR; gmp; SageMath; FLINT; OEIS; PARI/GP; MPFR; FDLIBM PDFBibTeX XMLCite \textit{F. Johansson}, LMS J. Comput. Math. 15, 341--359 (2012; Zbl 1344.11089) Full Text: DOI arXiv Digital Library of Mathematical Functions: §27.20 Methods of Computation: Other Number-Theoretic Functions ‣ Computation ‣ Chapter 27 Functions of Number Theory Online Encyclopedia of Integer Sequences: Number of partitions of 10^n. Number of decimal digits of A070177(n). 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.