Growth of k(n): runs of integers with a large prime factor > k (Erdős #962)
Statement
For a bound $n$, let $k(n)$ be the largest $k$ for which there exists $m\leq n$ such that each of the $k$ consecutive integers $$m+1,\ m+2,\ \ldots,\ m+k$$ is divisible by at least one prime $>k$. Estimate the growth of $k(n)$; in particular, is it true that $$\log k(n)\leq (\log n)^{1/2+o(1)}?$$
Acceptance. FULLY RESOLVES: a complete proof (or disproof) that $\log k(n)\leq(\log n)^{1/2+o(1)}$, written or machine-checkable (extending the existing formalisation). ADVANCES (each strictly beating the frontier stated in the background): (a) a nontrivial upper bound $k(n)\leq n^{1/2-c}$ for an explicit constant $c>0$ (open, per Erdős), or more generally any upper bound improving on Tao's $(1+o(1))n^{1/2}$ by a power of $n$; (b) an improved lower-bound constant, i.e. $\log k(n)\geq(c-o(1))\sqrt{\log n\,\log\log n}$ with an explicit $c>\tfrac1{\sqrt2}$, with proof; (c) extend the computed values of A327909 to a new record with a reproducible sieve and a certificate of the search's completeness. Deliver the proof, or the improved explicit constant with proof, or the search code plus the attained range.
Background
Asked by Erdős [Er65], [Er76e,p.273]; listed as open on erdosproblems.com/962 (fetched 2026-07-21, status 'open'). Erdős noted it is 'not hard' to show $\log k(n)\geq(\log n)^{1/2-o(1)}$, and in [Er76e] gave an argument for $\log k(n)\gg\sqrt{\log n\,\log\log n}$, which he thought fairly sharp. On the upper side: Terence Tao (in the site comments) gave a simple proof that $k(n)\leq(1+o(1))n^{1/2}$; Erdős [Er76e] reported he could prove $k(n)\leq\exp(-(\log n)^c)\,n^{1/2}$ for some $c>0$ but could NOT even show $k(n)\leq n^{1/2-c}$ for a constant $c>0$, which he called 'a ridiculously weak result'. The current record lower bound is due to Quanyu Tang: $\log k(n)\geq\left(\tfrac{1}{\sqrt 2}-o(1)\right)\sqrt{\log n\,\log\log n}$. The wide chasm between the $(\log n)^{1/2}$-scale lower bounds and the $n^{1/2}$-scale upper bounds is the crux; the conjecture asserts the truth is on the lower, $(\log n)^{1/2+o(1)}$ scale. Catalogued as OEIS A327909; a Lean formalisation exists in the DeepMind formal-conjectures project. Attacker's tool: sieve computation of $k(n)$ and the sequence A327909 (for each window, test divisibility of $m+1,\ldots,m+k$ by primes $>k$) to probe the conjecture and calibrate constants; analytic work on smooth-number and covering structure to break the $n^{1/2}$ upper barrier or to sharpen Tang's constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #962 (T. F. Bloom) | website |
| REF-02 | OEIS A327909 | website |
| REF-03 | Q. Tang, On Erdős Problem 962 (record lower bound) | paper |
| REF-04 | Lean formalisation of Erdős #962 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.