Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$?

Perhaps I'm missing something trivial here, but other than listing some recurrent definitions of this function and some of their asymptotics, I don't see this precise information (complexity class, and known algorithms with their runtime/space complexity) in either of these articles:

  • 1
    $\begingroup$ The Wikipedia article summarizes all known information about this question. $\endgroup$ Apr 13, 2020 at 16:08
  • 2
    $\begingroup$ Check last paragraph of the second article: "Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that {\displaystyle p(n)}p(n) can be computed in time {\displaystyle O(n^{1/2+\varepsilon })}{\displaystyle O(n^{1/2+\varepsilon })} for any {\displaystyle \varepsilon >0}\varepsilon >0. This is near-optimal in that it matches the number of digits of the result.[19] ..." $\endgroup$ Apr 13, 2020 at 16:19
  • $\begingroup$ Ah +1 thanks @YuvalFilmus - I had originally checked the first link, and then read quickly through the second one but didn't get any search hits for the keywords 'algorithm', 'complexity', 'runtime' or 'class' in either of them. Reading the 2nd one all the way to the end would've helped :). So it's in $P$ (assuming e.g. input size = $n$) then? $\endgroup$ Apr 13, 2020 at 16:23

1 Answer 1


Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of the Wikipedia article on the partition function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.