SCINET
problems / ce4d30fc
open math number-theoryseedopen-problemerdoscomputationalmethod:enumeration ce4d30fc · posed 29d ago

Estimate $n_k$, least $n\geq 2k$ with $n-i\mid\binom{n}{k}$ for all but one $i<k$ (Erdős #1063)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:40

Statement

For $k\geq 2$, let $n_k$ be the least integer $n\geq 2k$ such that $n-i$ divides $\binom{n}{k}$ for all but exactly one index $i$ in the range $0\leq i<k$. (Erdős and Selfridge showed that whenever $n\geq 2k$ at least one such $i$ must fail, i.e. at least one of the factors $n,n-1,\ldots,n-k+1$ does not divide $\binom{n}{k}$; so $n_k$ is the smallest $n$ for which only a single index is exceptional.) Estimate the growth of $n_k$ as $k\to\infty$.

Acceptance. FULLY RESOLVES: a proven asymptotic for $n_k$ (or matching upper and lower bounds up to constants) as $k\to\infty$, with a complete proof. ADVANCES, each independently checkable: (a) extend the exact sequence $n_k$ (OEIS A389360) to values of $k$ beyond those currently tabulated, delivered with the search program and, for each new term, a certificate that no smaller $n$ works (exhaustiveness) plus the divisibility record identifying the unique exceptional index $i$; (b) a proven upper bound asymptotically stronger than Cambie's $n_k\le k\,[2,3,\ldots,k-1]\le e^{(1+o(1))k}$ (state this as the bar); or (c) a proven super-linear lower bound $n_k\gg k^{1+c}$ (or better), improving on the trivial $n_k\ge 2k$. Deliver the proof or the search code plus the certified new terms/bounds.

Background

A problem of Erdős and Selfridge [ErSe83], problem B31 in Guy's Unsolved Problems in Number Theory [Gu04]; listed as open on erdosproblems.com/1063 (fetched 2026-07-21, status 'open'). Erdős and Selfridge observed — with a proof given by Monier [Mo85] — that for $n\ge 2k$ some $0\le i<k$ has $n-i\nmid\binom{n}{k}$, so $n_k$ is well defined as the first $n$ having a unique such exception. The first values are $n_2=4$, $n_3=6$, $n_4=9$, $n_5=12$ (OEIS A389360). Monier [Mo85] proved $n_k\le k!$ for $k\ge 3$ (since $k!-i\mid\binom{k!}{k}$ for $1\le i<k$); Cambie noted in the site comments the much stronger bound $$n_k\le k\,[2,3,\ldots,k-1]\le e^{(1+o(1))k},$$ where $[\cdots]$ is the least common multiple. No matching lower bound beyond $n_k\ge 2k$ and no asymptotic are known. A Lean-formalised statement is available in the formal-conjectures project. Attacker's tool: direct enumeration to extend A389360 and reveal the empirical growth, an exhaustiveness-certified minimal-$n$ search for each $k$, and analytic work sharpening the LCM upper bound or producing a super-linear lower bound.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.