Decomposing a Factorial into Large Factors

3/28/2025 at 5:56:53 PM

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

by SJC_Hacker

3/28/2025 at 6:47:41 PM

The naive way has to have a 1 in it since what you give only has 99 factors.

by dudinax

3/28/2025 at 7:11:21 PM

> 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?

by pansa2

3/28/2025 at 7:54:06 PM

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.

by SJC_Hacker

3/28/2025 at 4:12:14 PM

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.

by btilly

3/29/2025 at 7:06:47 PM

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!

by perihelions

3/28/2025 at 6:20:40 PM

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.

by dvh

3/28/2025 at 6:25:29 PM

https://en.wikipedia.org/wiki/Gamma_function

by HeliumHydride

3/28/2025 at 6:39:17 PM

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

by xinu2020

3/28/2025 at 10:42:20 PM

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.

by zamadatix

3/28/2025 at 7:39:24 PM

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.

by phkahler

3/28/2025 at 7:45:24 PM

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.

by madcaptenor

3/28/2025 at 8:20:01 PM

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

by Someone

3/28/2025 at 7:45:32 PM

N!! is pretty standard I think.

by thrasibule

3/28/2025 at 10:36:35 PM

Has anyone tried throwing a math-specialized LLM at this? I’m only half joking.

by kevinventullo

3/29/2025 at 5:12:20 AM

Unfortunately, we could only spare Erdős and Tao. ;)

by tibbar

3/28/2025 at 4:39:32 PM

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.

by zahlman

3/28/2025 at 5:02:10 PM

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

by intuitionist

3/29/2025 at 1:15:02 AM

Oh, that's much easier than I thought it would be. Nice job being rigorous, too.

by zahlman

3/28/2025 at 5:08:54 PM

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.

by tempodox

3/28/2025 at 5:32:45 PM

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

by btilly

3/28/2025 at 6:15:15 PM

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!

by vintermann

3/28/2025 at 5:22:25 PM

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.

by teraflop

3/29/2025 at 3:46:17 PM

It's a subset of the knapsack problem though, so there may well be some shortcut to solving it that doesn't let us solve arbitrary knapsacks.

by vintermann

3/30/2025 at 6:17:01 PM

Right, I was just trying to clarify because the OP was asking for a way to compute the function. It may not be the best way, and that's the interesting open question.

by teraflop

3/28/2025 at 5:29:40 PM

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))

by yorwba

3/28/2025 at 5:03:01 PM

[dead]

by curtisszmania

3/28/2025 at 3:53:42 PM

[flagged]

by Sharlin

3/28/2025 at 4:13:28 PM

Quoting the ask ...

> However, I was not able to adjust parameters to reach t(300000) >= 100000 in this manner. Perhaps some readers here who are adept with computers can come up with a more efficient construction to get closer to this bound? If one can find a way to reach this bound, most likely it can be adapted to then resolve conjectures (ii) and (iii) above after some additional numerical effort.

by rrauenza