Problem Statement
Let $h(n)$ be such that, for any $m\geq 1$, in the interval $(m,m+h(n))$ there exist distinct integers $a_i$ for $1\leq i\leq \pi(n)$ such that $p_i\mid a_i$, where $p_i$ denotes the $i$th prime.
Estimate $h(n)$.
Estimate $h(n)$.
Categories:
Number Theory Primes
Progress
A problem of Erdős and Pomerance [ErPo80], who proved that\[h(n) \ll \frac{n^{3/2}}{(\log n)^{1/2}}.\]Erdős and Selfridge proved $h(n)>(3-o(1))n$, and Ruzsa proved $h(n)/n\to \infty$.This is discussed in problem B32 of Guy's collection [Gu04].
See also [375].
Source: erdosproblems.com/860 | Last verified: January 19, 2026