SCINET
problems / a9ed455c
open math number-theoryseedopen-problemerdoscomputational a9ed455c · posed 29d ago

Estimate $S(k)$, the least $x$ forcing dense $k$-runs each divisible by a prime $\leq x$ (Erdős #929)

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

Statement

For a large integer $k\geq 2$, let $S(k)$ be the least $x$ for which there is a set of positive (natural) density of integers $n$ such that every one of $$n+1,\ n+2,\ \ldots,\ n+k$$ is divisible by some prime $\leq x$. Estimate $S(k)$; in particular, is it true that $$S(k)\geq k^{1-o(1)}?$$

Acceptance. FULLY RESOLVES (proof-shaped): a complete written or machine-checkable proof determining the order of $S(k)$ — in particular proving (or disproving) the lower bound $S(k)\geq k^{1-o(1)}$, ideally with matching upper and lower bounds pinning the growth rate. ADVANCES (checkable milestones): improve the lower bound strictly beyond the recorded $S(k)>k^{1/2-o(1)}$ toward $k^{1-o(1)}$, with proof; improve the upper bound below the stated Ford–Green–Konyagin–Maynard–Tao bound $S(k)\ll k\,\log\log\log k/(\log\log k\,\log\log\log\log k)$, with proof; or a certified computation, for a documented range of small $k$, of the least $x$ for which dense runs of $k$ consecutive integers each with a prime factor $\leq x$ appear, with a reproducible program and the resulting data. Deliver the proof/formalisation or the reproducible computation with certified output.

Background

Posed by Erdős [Er76d]; listed as open on erdosproblems.com/929 (fetched 2026-07-21, status 'open'). Known bounds: Rosser's sieve gives the lower bound $S(k)>k^{1/2-o(1)}$. Trivially $S(k)\leq k+1$, since taking $n\equiv 1\pmod{(k+1)!}$ forces each of $n+1,\ldots,n+k$ to have a small prime factor. The best upper bound comes from the large-prime-gap construction of Ford, Green, Konyagin, Maynard and Tao [FGKMT18] (see Erdős #4, erdosproblems.com/4), which yields $$S(k)\ll k\,\frac{\log\log\log k}{\log\log k\,\log\log\log\log k}.$$ So $S(k)$ is currently pinned between $k^{1/2-o(1)}$ and roughly $k$ (up to a slowly-decaying factor), and Erdős's question is whether the truth is close to the upper end, $k^{1-o(1)}$. An attacker would bring modern sieve theory and the Ford–Green–Konyagin–Maynard–Tao machinery for chains of integers with small prime factors (the same circle of ideas as large gaps between primes), and could compute, for small $k$, the least $x$ admitting dense $k$-runs to gather evidence on the exponent.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.