[HN Gopher] Decomposing a Factorial into Large Factors
___________________________________________________________________
Decomposing a Factorial into Large Factors
Author : surprisetalk
Score : 97 points
Date : 2025-03-28 14:55 UTC (8 hours ago)
(HTM) web link (terrytao.wordpress.com)
(TXT) w3m dump (terrytao.wordpress.com)
| btilly wrote:
| 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.
| zahlman wrote:
| From comments:
|
| >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
|
| Huh. Can we actually prove t(N) is monotonic? Jumps like that
| seem like they could be one-offs in some cases.
| intuitionist wrote:
| Yeah, since t(N) < N, you can use the decomposition for N! and
| one extra factor (N+1) to get a decomposition for (N+1)! with a
| smallest part equal to t(N).
| tempodox wrote:
| 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.
| teraflop wrote:
| 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.
| yorwba wrote:
| If you don't need it to be fast, the naive way to implement
| "the largest quantity such that it is possible to factorize N!
| into N factors a_1, ..., a_N, each of which is at least t(N)"
| is import math factorize = lambda N,
| number_of_factors: [(factor,) + rest for factor in range(1,
| N+1) if N % factor == 0 for rest in factorize(N//factor,
| number_of_factors-1)] if number_of_factors > 1 else [(N,)]
| t = lambda N: max(min(factors) for factors in
| factorize(math.factorial(N), N))
| btilly wrote:
| You factor N! into N factors, and look at the smallest of those
| factors. t(N) is the largest that the smallest factor can be.
| Here are the best factorizations going slightly beyond the part
| of https://oeis.org/A034258 that was quoted by Terry Tao.
| 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 4! = 2 *
| 2 * 2 * 3 5! = 2 * 2 * 2 * 3 * 5 6! = 2 * 2 * 3 *
| 3 * 4 * 5 7! = 2 * 2 * 3 * 3 * 4 * 5 * 7 8! = 2 *
| 3 * 3 * 4 * 4 * 4 * 5 * 7 9! = 3 * 3 * 3 * 4 * 4 * 4 * 5
| * 6 * 7 10! = 3 * 3 * 4 * 4 * 4 * 5 * 5 * 6 * 6 * 7
| 11! = 3 * 3 * 4 * 4 * 4 * 5 * 5 * 6 * 6 * 7 * 11 12! = 3
| * 4 * 4 * 4 * 5 * 5 * 6 * 6 * 6 * 6 * 7 * 11 13! = 3 * 4
| * 4 * 4 * 5 * 5 * 6 * 6 * 6 * 6 * 7 * 11 * 13 14! = 4 *
| 4 * 4 * 5 * 5 * 6 * 6 * 6 * 6 * 6 * 7 * 7 * 11 * 13 15!
| = 4 * 5 * 5 * 5 * 6 * 6 * 6 * 6 * 6 * 6 * 7 * 7 * 8 * 11 *
| 13 16! = 5 * 5 * 5 * 6 * 6 * 6 * 6 * 6 * 6 * 7 * 7 * 8
| * 8 * 8 * 11 * 13
| vintermann wrote:
| Is the number of factors when you write it out this way,
| always one more than the previous?
|
| EDIT: Never mind, that's part of the definition of the
| problem!
| SJC_Hacker wrote:
| 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
|
| The "naive" way 100!= 2*3*4*...*99*100
|
| 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),
| 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
|
| 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
| 100! = 4*4*5*...*9*9*10*..*33*33*...*50*50...*97*98
|
| 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.
|
| 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.*
| dudinax wrote:
| The naive way has to have a 1 in it since what you give only
| has 99 factors.
| pansa2 wrote:
| > 100 = 3*4*...*50*50*...99
|
| You can't replace 2*100 with 50, it has to be 4*50. But there's
| no reason you have to divide by 2 at all - why not replace 2*99
| with 6*33?
| SJC_Hacker wrote:
| Thanks, I've fixed the idea
|
| The basic idea is to "pair" the lowest numbers with the
| highest ones - sort of pushing everything towards the middle
| values
|
| Like I said, its naive greedy and non-optimal - otherwise
| time would be linear.
| dvh wrote:
| 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.
| HeliumHydride wrote:
| https://en.wikipedia.org/wiki/Gamma_function
| xinu2020 wrote:
| For those who are curious how we can construct such a
| function, and why it looks so funky on the negative side, I
| strongly recommend this video
| https://www.youtube.com/watch?v=v_HeaeUUOnc
| zamadatix wrote:
| I think they mean a (traditionally) closed form expression,
| for which I don't know if there is a particularly simple
| explanation of why there isn't such a form but there is for
| summing integers to n instead of multiplying them.
| phkahler wrote:
| 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.
| madcaptenor wrote:
| N!! is the usual notation, so 3!! = 3, 4!! = 8, 5!! = 15, 6!! =
| 48, etc.
|
| It's a bit unfortunate, because you'd think it meant iterating
| the factorial, so 3!! = 720, etc. But there are basically no
| situations where you want to do that.
| thrasibule wrote:
| N!! is pretty standard I think.
| Someone wrote:
| > but there is no simple formula for the product of the odd
| numbers.
|
| There is. It is _N!_ divided by the product of all even numbers
| up to _N_.
| kevinventullo wrote:
| Has anyone tried throwing a math-specialized LLM at this? I'm
| only half joking.
___________________________________________________________________
(page generated 2025-03-28 23:00 UTC)