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 \cite{Iw78},\[Y(x) \ll x^2.\]The best lower bound is due to Ford, Green, Konyagin, Maynard, and Tao \cite{FGKMT18},\[Y(x) \gg x\frac{\log x\log\log\log x}{\log\log x},\]improving on a previous bound of Rankin \cite{Ra38}.

Maier and Pomerance have conjectured that $Y(x)\ll x(\log x)^{2+o(1)}$.

In \cite{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 \cite{Er80} Erd\H{o}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].


References


[Er80] Erd\H{o}s, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.

[FGKMT18] Ford, Kevin and Green, Ben and Konyagin, Sergei and Maynard, James and Tao, Terence, Long gaps between primes. J. Amer. Math. Soc. (2018), 65-105.

[Iw78] Iwaniec, Henryk, On the problem of {J}acobsthal. Demonstratio Math. (1978), 225--231.

[Ra38] Rankin, R. A., The Difference between Consecutive Prime Numbers. J. London Math. Soc. (1938), 242-247.