5 ms·

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 2y ago
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.
- vintermann 2y ago
  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.
  - teraflop 2y ago
    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.
yorwba 2y ago
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 2y ago
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 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
- deleted 2y ago
  [deleted]
- vintermann 2y ago
  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!
- deleted 2y ago
  [deleted]

teraflop 2y ago

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.

vintermann 2y ago
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.
- teraflop 2y ago
  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.

yorwba 2y ago

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 2y ago

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

deleted 2y ago
[deleted]
vintermann 2y ago
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!
deleted 2y ago
[deleted]