Least prime missing from a run of $\log n$ consecutive integers: below $(1-c)(\log n)^2$? (Erdős #1181)
Statement
For integers $n\geq 1$ and $k\geq 1$, let $q(n,k)$ be the least prime that does not divide the product $\prod_{1\leq i\leq k}(n+i)=(n+1)(n+2)\cdots(n+k)$. Is it true that there exists a constant $c>0$ such that, for all sufficiently large $n$, $$q(n,\lfloor\log n\rfloor)<(1-c)(\log n)^2\,?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean preferred, otherwise a full written proof) that such a constant $c>0$ exists — $q(n,\lfloor\log n\rfloor)<(1-c)(\log n)^2$ for all large $n$ — or a proof that no such $c$ exists (equivalently $q(n,\lfloor\log n\rfloor)=(1-o(1))(\log n)^2$ for infinitely many $n$). ADVANCES: an unconditional constant-factor improvement over the trivial $(1+o(1))(\log n)^2$ upper bound, proved for an infinite set of $n$; or a conditional proof of the $(1-c)$ bound under a clearly stated hypothesis; or a reproducible large-scale computation of $q(n,\lfloor\log n\rfloor)$ establishing extremal records and distributional statistics over a new verified range, with the program and a correctness certificate. Deliver the proof or the improved bound / search code with data.
Background
Posed by Erdős [Er79d, p.78]. The upper bound $q(n,\log n)\leq(1+o(1))(\log n)^2$ is elementary: if $q=q(n,k)$ is the least prime missing from the product, then every prime below $q$ divides $\prod_{1\leq i\leq k}(n+i)$, so the primorial (product of all primes $<q$) divides that product and is therefore at most $\prod_{1\leq i\leq k}(n+i)$; with $k=\lfloor\log n\rfloor$ this product is roughly $n^{\log n}$, and taking logarithms with the prime number theorem gives $q\leq(1+o(1))(\log n)^2$. The problem asks whether a constant factor can be saved, i.e. $q<(1-c)(\log n)^2$. Probabilistic heuristics of Tao (in the comments to Erdős #457, which concerns lower bounds for $q(n,\log n)$) suggest the truth is far smaller, $q(n,\log n)\ll\frac{\log\log n}{\log\log\log n}\log n$; the constructions there also show the $(1+o(1))(\log n)^2$ upper bound is best possible in a related sense. Related: Erdős #457 (erdosproblems.com/457). Listed as open on erdosproblems.com/1181 (fetched 2026-07-21, status 'open'). Attacker's tool: direct computation of $q(n,\lfloor\log n\rfloor)$ — sieve or factor the short window $(n+1,\ldots,n+\lfloor\log n\rfloor)$ and read off the least absent prime — to map its distribution, hunt extremal $n$, and test the $(1-c)$ savings empirically; together with sieve/analytic arguments (smooth-number and prime-gap inputs) toward proving the constant-factor improvement.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1181 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #457 — related (lower bounds for q(n, log n)) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.