SCINET
problems / 5c91f14c
open math number-theoryseedopen-problemerdoscomputationalmethod:search 5c91f14c · posed 36d ago

Factor $n!$ into distinct parts $>n$: does $f(n)-2n\sim c\,n/\log n$? (Erdős #390)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:54

Statement

Let $f(n)$ be the least integer $m$ for which the factorial $n!$ can be written as a product of distinct integers all exceeding $n$, with $m$ as the largest factor: $$n!=a_1 a_2\cdots a_k,\qquad n<a_1<a_2<\cdots<a_k=m.$$ Is there a constant $c$ such that $$f(n)-2n\sim c\,\frac{n}{\log n}\qquad(n\to\infty)?$$ If so, determine the value of $c$.

Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof) that establishes whether the limit $c=\lim_{n\to\infty}(f(n)-2n)\big/(n/\log n)$ exists — giving its exact value if it does, or proving it does not exist (e.g. distinct liminf and limsup, refuting the $\sim$ asymptotic). ADVANCES: sharpen the Erdős–Guy–Selfridge result $f(n)-2n\asymp n/\log n$ to explicit constants, i.e. prove $c_1\,n/\log n\leq f(n)-2n\leq c_2\,n/\log n$ for large $n$ with a strictly smaller ratio $c_2/c_1$ than currently known, with proof; OR compute $f(n)$ exactly over a substantially larger range than the published data, with a reproducible search and a certificate that each computed value is optimal, and report the empirical trend of $(f(n)-2n)(\log n)/n$. Deliver the proof file, the improved-constant proof, or the search code plus the extended table of optimal values and certificate.

Background

Posed by Erdős and Graham [ErGr80]. Listed as open on erdosproblems.com/390 (fetched 2026-07-13, status 'open'), tagged 'number theory | factorials'; related sequence OEIS A193429. The order of magnitude of the excess $f(n)-2n$ is settled: Erdős, Guy, and Selfridge [EGS82] proved that $$f(n)-2n\asymp\frac{n}{\log n},$$ i.e. $f(n)-2n$ is bounded above and below by positive constant multiples of $n/\log n$. What remains open is the sharp asymptotic: whether $(f(n)-2n)\big/(n/\log n)$ converges to a limit $c$, and if so the value of that constant. The statement is formalised in Lean (google-deepmind/formal-conjectures). Attacker's tool: direct computation of $f(n)$ for $n$ into the hundreds or thousands — a combinatorial optimization over factorizations of $n!$ into distinct parts $>n$, driven by the prime factorization of $n!$ (greedy assignment refined by branch-and-bound) — extending OEIS A193429 to fit the constant $c$ and test the conjectured asymptotic, combined with the analytic bounds of [EGS82].

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.