Re:Decomposing a Factorial into Large Factors
by vintermann on Saturday March 29, 2025 @11:46AM
(#43516404)
It'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.
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.