3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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})$.

$\endgroup$

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.