Problem Statement
Let $k(n)$ be the maximal $k$ such that there exists $m\leq n$ such that each of the integers\[m+1,\ldots,m+k\]are divisible by at least one prime $>k$. Estimate $k(n)$.
Categories:
Number Theory
Progress
Erdős [Er65] wrote it is 'not hard to prove' that\[k(n)\gg_\epsilon \exp((\log n)^{1/2-\epsilon})\]and it 'seems likely' that $k(n)=o(n^\epsilon)$, but had no non-trivial upper bound for $k(n)$.It is not clear what he meant by a non-trivial bound for this problem, but Tao in the comments has given a simple argument proving $k(n) \leq (1+o(1))n^{1/2}$.
Tang has proved a lower bound of\[k(n)\geq \exp\left(\left(\frac{1}{\sqrt{2}}-o(1)\right)\sqrt{\log n\log\log n}\right).\]
Source: erdosproblems.com/962 | Last verified: January 19, 2026