OPEN
This is open, and cannot be resolved with a finite computation.
- $1000
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)}$?
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].
View the LaTeX source
This page was last edited 06 December 2025.
Additional thanks to: Boris Alexeev, Stijn Cambie, Wouter van Doorn, and Desmond Weisenberg
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #687, https://www.erdosproblems.com/687, accessed 2026-01-16
