5
$\begingroup$

Rademacher’s formula for the partition function allows fast computation using high precision arithmetic, but requiring a lot of memory. Here is an example computation of $p(10^{20})$ by Fredrik Johansson.

Question: Is there a $p$-adic or modular analogue that allows fast computation modulo an arbitrary small prime, with low memory (related only to the size of the prime)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

To the best of my knowledge, there is no known method to compute $p(n)$ modulo a small prime using less than $n^{1/2+o(1)}$ time or memory, except for those cases where a Ramanujan-like congruence applies.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hi, could you share how to compute it in $O(n^{1/2+o(1)})$? $\endgroup$
    – Oleksandr Kulkov
    Commented Apr 16, 2023 at 13:57
  • $\begingroup$ Using the Rademacher series; see the links in the question. $\endgroup$
    – Fredrik Johansson
    Commented Apr 16, 2023 at 14:00
  • 1
    $\begingroup$ Though fredrikj.net/math/hrr.html has a lot more details. :) $\endgroup$
    – Geoffrey Irving
    Commented Apr 16, 2023 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .