4 ms·
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
by btilly 2y ago
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.
- deleted 2y ago[deleted]
- perihelions 2y agoOut 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!