Is it possible to generate all multiplicative partitions of $n$ in time $2^{o(\log n)}$?
$o(\cdot)$ is "small O" notation.
Asked
Active
Viewed 53 times
0
-
Two first thoughts, not necessarily useful or correct. Isn't that bound essentially just $n$? I think you have to factor $n$ first. Then: why do you need to know? How large will $n$ be in practice (if it's a practical matter)> – Ethan Bolker May 06 '18 at 18:02
-
This is a theoretical question. Numbers ($n$) are to aim for infinity. – Aurelio May 06 '18 at 18:06
-
We can assume that the factors is available from outside (eg from a quantum computer - Shor algorithm). – Aurelio May 06 '18 at 18:09
-
If $n$ is $k$-th primorial then just the number of multiplicative partitions of $n$ is $k$-th Bell number. The $k\to\infty$ asymptotics of logarithms of these coinside, right? (It is towards the negative answer.) – metamorphy May 06 '18 at 18:16