The least integer not dividing $\binom{2n}{n}$: pin down its typical growth rate (Erdős #731)
Statement
For $n\geq 1$ let $m(n)$ be the least integer $m\geq 2$ such that $m\nmid\binom{2n}{n}$. Find some reasonable (explicit) function $f(n)$ such that, for almost all integers $n$ (i.e. on a set of density $1$), $$m(n)\sim f(n).$$
Acceptance. FULLY RESOLVES: an explicit function $f(n)$ together with a proof that $m(n)/f(n)\to 1$ on a set of $n$ of density $1$; a proof determining the almost-sure asymptotic at any equivalent precision (e.g. $m(n)=\exp((c+o(1))(\log n)^{1/2})$ for an explicit constant $c$, if that is the truth) also fully resolves, as does a proof that no such concentration holds (i.e. that $m(n)$ does not have an almost-sure asymptotic). Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: (a) any strict sharpening, with proof, of the known window $m(n)=\exp((\log n)^{1/2+o(1)})$ stated in the background (e.g. bounding the second-order term); (b) a large-scale reproducible computation of $m(n)$ (carry-criterion code, stated range $n\leq N$) that extends OEIS A006197 beyond its published terms and delivers an empirically supported explicit conjecture for $f(n)$ with error analysis; (c) a proof of the almost-sure asymptotic restricted to prime-power scales (e.g. determining the typical size of the least prime power failing to divide $\binom{2n}{n}$ for primes in a fixed range). Deliver the proof file, or the code plus data tables and the fitted conjecture.
Background
A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75]; listed as open on erdosproblems.com/731 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). EGRS75 remark it is 'not hard to show' that for almost all $n$ the minimal such $m$ satisfies $m=\exp((\log n)^{1/2+o(1)})$; the problem asks to pin the asymptotic inside this coarse window. Structure making the problem concrete: the least non-divisor of any integer is always a prime power, and by Kummer's theorem $v_p(\binom{2n}{n})$ equals the number of carries when adding $n+n$ in base $p$, so $m(n)$ is computable quickly without ever forming $\binom{2n}{n}$; the values are tracked in OEIS A006197. A resolution amounts to proving that the least non-divisor concentrates at a precise scale $f(n)$, which requires joint equidistribution of base-$p$ carry statistics over many prime powers. The attacker's tool: compute $m(n)$ for $n$ up to $10^8$ and beyond via the carry criterion, extend OEIS A006197, and fit $\log m(n)$ against $(\log n)^{1/2}$-scale normalisations to produce a data-backed precise conjecture for $f$; on the proof side, sharpen the $o(1)$ in the EGRS exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #731 (T. F. Bloom) | website |
| REF-02 | OEIS A006197 — related sequence: least m not dividing the central binomial coefficient C(2n,n) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.