Decomposing a Factorial into Large Factors

Re:Decomposing a Factorial into Large Factors by btilly on Friday March 28, 2025 @12:12PM (#43507147)

Out of curiosity, I wondered how tight these bounds are. Consider the case of 300,000 which Terry has put a lower bound of 90,000 on, and would like a bound of 100,000 on. If a perfect division of factors into equal buckets could be achieved, the answer would be 110366.49020484093 per bucket. That's e^(log(n!)/n), to within the precision that Python calculates it. (My first try was to use Stirling's formula. That estimated it at 110366.49020476094, which is pretty darned close!)

A straightforward greedy approach will see those final buckets differing by factors of around 2. Which is a lot worse than Terry's current approach.

This really is a knapsack problem.

[ Parent | on HN ]

Re:Decomposing a Factorial into Large Factors by perihelions on Saturday March 29, 2025 @03:06PM (#43517727)

Out of curiosity, which greedy approach did you use? There's more than one.

The first one I tried did poorly: I start with a goal t*, and append all remaining factors of N!, starting with t* and increasing greedily. That terminates in a very suboptimal place, where you're left with a bunch of large prime factors p_i < t*, such that all pairs p_i * p_j >> t* ("much greater than") — there's a large amount of wasted "slack". The optimal solution should probably pair the largest primes with small multipliers.

I'm curious what other people have tried!

[ Parent | on HN ]