The total number of ways a positive number $n$ can be partitioned is called the partition number $p(n)$. The best algorithm I found on the internet is a dynamic programming implementation of Euler's pentagonal formula. Is there any proof that there cannot be any better algorithm? Is there any better algorithm already?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Fredrik Johansson showed in his work Efficient implementation of the Hardy-Ramanujan-Rademacher formula how to compute $p(n)$ in time $O(\sqrt{n} \log^{4+o(1)} n)$ (the recent optimal integer multiplication algorithm might result in a removal of the $\log^{o(1)} n$ factor). This is nearly optimal, since the output length is $\Theta(\sqrt{n})$.
answered Mar 5, 2022 at 21:33