Problem 687

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)}$ ?

Source: erdosproblems.com/687

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open. No source proving $Y(x)=o(x^2)$ , or any upper bound below Iwaniec's $Y(x)\ll x^2$ , was found in the search whose scope the Current assessment records. The bounds in hand: $Y(x)\ll x^2$ (the Corollary of [Iw78], p. 226, $C(r)\ll r^2\log^2r$ for the longest run of consecutive integers each divisible by one of $r$ arbitrary primes, taken at $r=\pi(x)$ ; attested in this form by the introduction of [FGKMT18] and, in the inverse form $B(n)>c\sqrt n$ , by [Er79d] p. 79); $Y(x)\gg x\log x\log_3x/\log_2x$ (display (1.2) of [FGKMT18], J. Amer. Math. Soc. 2018, refereed, cited from the arXiv version), improving Rankin's $x\log x\log_3x/(\log_2x)^2$ ; and the site's account, since 31 August 2026, of a further improvement $Y(x)\gg x\log x/\log_3x$ attributed to GPT 5.6 Pro (the name the site gives) prompted by a forum contributor, supported by a proof claim and a maintainer's exposition on the site's Problem 4 page and recorded here as the site's account, not as a refereed result. The conjectured truth is $Y(x)\ll x(\log x)^{2+o(1)}$ (Maier and Pomerance, as attested by [FGKMT18]); Erdős expected $B(n)>n^{1-\varepsilon}$ . This is a bounded negative finding, not a certificate of openness. Since that search, the OpenAI mathematics release of 25 September 2026 claims $h(k)\ll k^2/(\log\log3k)^2$ for Jacobsthal's function; its Theorem 1.2 states the covering form directly, $Y(z)<z^2/(\log z)^2$ for large $z$ , a yes to the first displayed question if it stands, without naming $Y(x)$ or this problem. The manuscript is unreviewed, and the Lean declaration the corpus built and audited concerns $h(k)$ alone, so it is a pending partial claim on its claim page (OpenAI, 2026) and the standing stays open. Erdős's offer in [Er80] p. 106 is a prize "for clearing up of this problem", and the site lists a prize.

FGKMT18: Ford, K., Green, B., Konyagin, S., Maynard, J. and Tao, T., Long gaps between primes. J. Amer. Math. Soc. 31 (2018), no. 1, 65--105, DOI 10.1090/jams/876 (published online 23 February 2017, per the Crossref record); arXiv:1412.5029v3 (14 July 2016, 40 pp.; the locators are the arXiv version's). Theorem 1, p. 2; Definition 1, Lemma 1.1 and (1.2), p. 3; (1.3) and the upper bounds, p. 4. Library home: Ford et al. 2018; result pages Theorem 1, display (1.2) and Lemma 1.1 with (1.3).
Iw78: Iwaniec, H., On the problem of Jacobsthal. Demonstratio Math. 11 (1978), no. 1, 225--231, DOI 10.1515/dema-1978-0121 (the printed pages; the Crossref record's 225--232 counts the blank page after the article). The definition of $C(r)$ on printed p. 225 and the Theorem and Corollary on p. 226. Library home: Iwaniec 1978; result pages Theorem and Corollary.
Er79d: Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. 33 (1979), 71--80; Section 3, the $B(n)$ passage on printed p. 79. Library home: Erdos 1979; result page Section 3.
Er80: Erdős, P., A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; Section 6, item 1, printed p. 106. Library home: Erdos 1980.
Er96b: Erdős, P., Some problems I presented or planned to present in my short talk. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995), Progr. Math. 138, Birkhäuser (1996), 333--335. Not held: past the Rényi archive's cutoff, no open copy known, no request made. Its passage is not known here.
Ra38: Rankin, R. A., The difference between consecutive prime numbers. J. London Math. Soc. 13 (1938), 242--247. Not held (closed access; no request made); its covering bound $Y(x)\gg x\log x\log_3x/(\log_2x)^2$ is quoted from [FGKMT18] p. 4 and its inverse form from [Er79d] p. 79. Context only.
Gr26: Green, B., 100 open problems. Author's list, PDF compiled 30 January 2026, 62 pp.; Problem 46, p. 23 (the author's page, accessed 2026-09-18; library home Green 2026). Context.

Problem 687

Status

Proof claims

Discussion