Edit: as pointed out, you can't simply divide by each number, because then its not equal to original number factorial. However, I've fixed the algorithm somewhat maintaining the basic idea<p>The "naive" way<p><pre><code> 100!= 2*3*4*...*99*100
</code></pre>
Obviously t(100) > 1. If we can get rid of the single 2, we know that t(100) > 2. If you multiply the whole thing by 2/2 (=1),<p><pre><code> 100! = (2/2)*2*3*4*...*50*...99*100
= (2*2/2)*3*4*...*50*...99*100
= (4/2)*3*4*...*50*...99*100
= 4*3*4*...*50*...99*(100/2)
= 3*4*4*...*50*50*...99
</code></pre>
We can continue with t(100) > 3 by multiplying by 3/3 and pairing it with 99, i.e. 99*3*(3/3) = (99/3)*3*3 = 33*9 yielding<p><pre><code> 100! = 4*4*5*...*9*9*10*..*33*33*...*50*50...*97*98
</code></pre>
However, once we get to t(100) > 4, trying to get rid of 4, we have to skip 98 since its not divisible by 4. The other problem is we have two 4s... If we had instead using 98 for getting rid of 2, we can then use 100, and 96 for the other 4. This is our first "gotcha" for the naive algorithm of always picking the largest number, which seems intuitive at first glance.<p>Now if we test all possibilities starting with 2, we get 48 choices for the dividing 2 (even numbers > 2, not including 2 which will not increase t(100) beyond 2. Then ~33 choices for dividing 3 (depending if our div of 2 resulted in a factor of 3), ~25 for 4, But notice since we now have two 4s, we have to do it twice, so its 25*24 choices for getting rid of 4.*
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!)<p>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.<p>This really is a knapsack problem.
As a kid I was bugged by the fact that Stirling formula doesn't give exact integer result, so I set to find my own formula. I failed, but discovered that sum from 1 to N is (n*n+n)/2. Surely if perfect formula for sum exists, for multiplication should exist too.
Is there a standard notation for the product of all even numbers up to N and for the product of all odd numbers up to N? I know if N is even then the product of evens is = (N/2)! * 2^(N/2) so I guess notation for that is a little redundant, but there is no simple formula for the product of the odd numbers.
From comments:<p>>No; in fact, in Guy’s article on this problem, he notes that there is a jump of 2 from t(124)=35 to t(125)=37<p>Huh. Can we actually prove t(N) is monotonic? Jumps like that seem like they could be one-offs in some cases.
I'm still confused as to how to compute t(N). Maybe it's buried in the legalese of this text and I'm just dumb, but I can't find a clue.