2 ms·
The straightforward but slow way is to just brute-force over all possible factorizations of N!. As the post states, writing N! as a product of factors is equiv
by teraflop 2y ago
The straightforward but slow way is to just brute-force over all possible factorizations of N!.
As the post states, writing N! as a product of factors is equivalent to writing log(N!) as a sum of those factors' logarithms. So log(t(N)) is the smallest bin size such that the factors all "fit" into N bins of that size.
This computation is simple to describe and implement, it's just inefficient because there's a combinatorial explosion of possible ways to pack factors into bins. It's an instance of the knapsack problem which is NP-complete.
- vintermann 2y agoIt's a subset of the knapsack problem though, so there may well be some shortcut to solving it that doesn't let us solve arbitrary knapsacks.
- teraflop 2y agoRight, I was just trying to clarify because the OP was asking for a way to compute the function. It may not be the best way, and that's the interesting open question.