Problem 390. Factorizing $n!$ into distinct integers larger than $n$ and the constant $c$
Formal restatement
For each $n\ge 1$, define $f(n)$ to be the least integer $m$ for which there exist integers \[
n<a_1<a_2<\cdots<a_k=m
\] with
\begin{equation}
\label{wsref-0-65-71-3a-50-33-39-30-2d-64-65-66}
n! = a_1 a_2\cdots a_k.
\end{equation} (Equivalently, $\{a_1,\dots,a_k\}$ is a set of distinct integers all lying in $(n,m]$ whose product is $n!$.) The problem asks:
Given that $f(n)-2n\asymp n/\log n$ (two-sided order of magnitude), does there exist a constant $c$ such that \[
f(n)-2n\sim c\,\frac{n}{\log n}\qquad(n\to\infty)?
\]
Quick literature/context check (browsing available)
Erdős, Guy, and Selfridge $1982$ prove two-sided bounds of the shape \[
2n+c_1\frac{n}{\log n}\ \le\ f(n)\ \le\ 2n+c_2\frac{n}{\log n}
\] for sufficiently large $n$ (in particular $f(n)-2n=\Theta(n/\log n)$), with explicit constants obtainable from their argument. The Erdős Problems site (Problem #390) states that the existence/value of a limiting constant $c$ remains open.
Attack plan
- Understand the "baseline" $2n$ barrier: explain why trying to realize (eq:P390-def) using only numbers in $(n,2n]$ is sometimes impossible.
- Summarize the mechanism behind the known $\Theta(n/\log n)$ bounds: relate the problem to factoring the central binomial coefficient $\binom{2n}{n}$ into distinct integers in $(n,2n]$ and accounting for leftover small-prime powers.
- Attempt to isolate the main term that would determine the constant $c$ (if it exists), and identify the bottleneck that prevents a clean asymptotic.
Work
A convenient reformulation via $\binom{2n}{n}$.
We have the identity
\begin{equation}
\label{wsref-0-65-71-3a-50-33-39-30-2d-63-65-6e-74-72-61-6c}
\binom{2n}{n}=\frac{(n+1)(n+2)\cdots(2n)}{n!}.
\end{equation} Equivalently,
\begin{equation}
\label{wsref-0-65-71-3a-50-33-39-30-2d-70-72-6f-64}
(n+1)(n+2)\cdots(2n)=n!\,\binom{2n}{n}.
\end{equation} If one could choose a subset $B\subseteq\{n+1,\dots,2n\}$ with $\prod_{b\in B} b=\binom{2n}{n}$, then dividing
(eq:P390-prod) by that product would give \[
n!=\prod_{c\in\{n+1,\dots,2n\}\setminus B} c,
\] which would realize
(eq:P390-def) with $m\le 2n$. Thus $f(n)>2n$ exactly when $\binom{2n}{n}$ cannot be expressed as a product of distinct integers all lying in $(n,2n]$.
Why $f(n)$ is close to $2n$.
The set $(n,2n]$ already contains one copy of every prime in $(n,2n]$, many composites, and many even numbers; heuristically this makes it plausible to "absorb" most of the prime-power content of $\binom{2n}{n}$ using a subset of $(n,2n]$, leaving only a relatively small leftover supported on small primes (notably powers of $2$). The leftover can then be absorbed by extending the allowed range from $2n$ up to $2n+H$ and including additional numbers $>2n$ that carry the needed small-prime power.
Known bounds (as a black box).
Erdős--Guy--Selfridge obtain constants $c_1,c_2>0$ such that
\begin{equation}
\label{wsref-0-65-71-3a-50-33-39-30-2d-61-73-79-6d-70}
f(n)=2n+\Theta\!\left(\frac{n}{\log n}\right).
\end{equation} Their upper bound strategy (roughly) constructs the needed factorization by selecting suitable elements of $(n,2n]$ to account for all odd primes, leaving a deficit in powers of $2$; this deficit is then handled by "doubling" certain selected terms, pushing the maximal factor from $2n$ up to $2n+O(n/\log n)$. Their lower bound strategy finds many primes $p$ in a subinterval of $(n,2n]$ for which one must pay (at least) one extra factor of $2$ or $3$ beyond $2n$, forcing $f(n)\ge 2n+\Omega(n/\log n)$.
Where the constant $c$ would come from.
If one could show that, after optimally choosing the subset $B\subset(n,2n]$ in
(eq:P390-prod), the leftover is typically a power of $2$ of size $2^{\alpha n/\log n+o(n/\log n)}$, and that the most efficient way to absorb it requires extending to $2n+\beta n/\log n+o(n/\log n)$, then one would obtain a candidate constant $c=\beta$. However, making this rigorous seems to require fine control over how prime powers appear in $\binom{2n}{n}$ and how efficiently they can be packaged into distinct integers in short intervals.
Verification
- (eq:P390-central) is the standard formula for the central binomial coefficient.
- The reformulation in terms of selecting a subset $B\subset(n,2n]$ is a direct algebraic rearrangement of (eq:P390-prod).
Final
UNRESOLVED. - (i) Strongest proved partial result: The known theorem of Erdős--Guy--Selfridge gives $f(n)=2n+\Theta(n/\log n)$, i.e. (eq:P390-asymp).
- (ii) First gap / obstruction: To prove the existence of a limit constant $c$ (or to disprove it) one needs substantially sharper control on the optimal packaging of the prime-power content of $\binom{2n}{n}$ into distinct integers in $(n,2n]$ and on the minimal "overhang" beyond $2n$ needed to absorb the leftover. The available arguments give only coarse $\Theta(\cdot)$ bounds.
- (iii) Top 3 next moves: $1$ Develop an "optimal transport" viewpoint for prime powers from $\binom{2n}{n}$ into $(n,2n]$ and $(2n,2n+H]$, and prove a limit shape for the leftover. $2$ Improve both upper and lower bounds by using several small primes (not just $2$) in the absorption step, potentially tightening $c_1,c_2$ toward a common value. $3$ Investigate whether $\left(f(n)-2n\right)\log n/n$ exhibits persistent oscillation (e.g. depending on prime distribution in short intervals), which would rule out the existence of a limit.
- (iv) What a minimal counterexample would look like: If the limit does not exist, one would expect two sequences $n_t$ and $n'_t$ along which the optimal leftover after the best choice of $B$ has systematically different size (or different small-prime structure), forcing different limiting values for $(f(n)-2n)\log n/n$.
Completion estimate
A full resolution requires either: (a) a proof that $(f(n)-2n)\log n/n$ converges and identification of its limit, or (b) a proof of divergence/oscillation. Both appear to need a refined structural theory for factorizing $\binom{2n}{n}$ into distinct integers constrained to lie in a short interval.