News for hackers. Stuff that matters.
Re:Decomposing a Factorial into Large Factors by teraflop on Friday March 28, 2025 @01:22PM (#43507925)
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.

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.
Re:Decomposing a Factorial into Large Factors by teraflop on Sunday March 30, 2025 @02:17PM (#43526275)
Right, 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.