Algorithmic consequences of algebraic formula for partition function?

Question

Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic consequences for fast computation of the partition function?

Answer 1

It is my uninformed belief that Rademacher's formula is faster in practice (and perhaps in theory also) than the Bruinier and Ono formula. While Rademacher's asymptotic expansion is an infinite sum, we know that $p(n)$ is an integer, so if we have bounds on the tails of the expansion, we can use the formula to compute $p(n)$. According to Calkin et al., "the exact formula of Rademacher yields a very fast algorithm".

Bruinier and Ono describe what would take to implement their algorithm in Section 5 of their paper. The first step is to determine representatives for $\mathcal{Q}_n$, of which there are $h(-24n+1)$. According to Soundararajan, we should expect $h(-24n+1) = \Theta(n)$, so the formula would involve $\Theta(n)$ summands. That makes it worse than Euler's formula for $p(n)$ (computationally speaking), though the latter admittedly requires $\Omega(n)$ memory.