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.
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!