Problem Statement
Let $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $p\leq x$ such that every integer in $[1,y]$ is congruent to at least one of the $a_p\pmod{p}$.
Give good estimates for $Y(x)$. In particular, can one prove that $Y(x)=o(x^2)$ or even $Y(x)\ll x^{1+o(1)}$?
Give good estimates for $Y(x)$. In particular, can one prove that $Y(x)=o(x^2)$ or even $Y(x)\ll x^{1+o(1)}$?
Categories:
Number Theory
Progress
This function (associated with Jacobsthal) is closely related to the problem of gaps between primes (see [4]). The best known upper bound is due to Iwaniec [Iw78],\[Y(x) \ll x^2.\]The best lower bound is due to Ford, Green, Konyagin, Maynard, and Tao [FGKMT18],\[Y(x) \gg x\frac{\log x\log\log\log x}{\log\log x},\]improving on a previous bound of Rankin [Ra38].Maier and Pomerance have conjectured that $Y(x)\ll x(\log x)^{2+o(1)}$.
In [Er80] he writes 'It is not clear who first formulated this problem - probably many of us did it independently. I offer the maximum of \$1000 dollars and $1/2$ my total savings for clearing up of this problem.'
In [Er80] Erdős also asks about a weaker variant in which all except $o(y/\log y)$ of the integers in $[1,y]$ are congruent to at least one of the $a_p\pmod{p}$, and in particular asks if the answer is very different.
See also [688] and [689]. A more general Jacobsthal function is the focus of [970].
Source: erdosproblems.com/687 | Last verified: January 16, 2026