Jacobsthal's problem: covering an interval by one residue class per prime
Note: A stronger lower bound, Y(x) ≫ x log x / log log log x, is credited to GPT 5.6 Pro on erdosproblems.com (#4, #687); no paper of it is linked here.
Let $Y(x)$ be the largest integer $y$ such that $\{1, \dots, y\}$ can be covered by residue classes $a_p \pmod p$, one for each prime $p \le x$. Ford, Green, Konyagin, Maynard and Tao proved $Y(x) \gg x \frac{\log x \log \log \log x}{\log \log x}$, a bound tied to large gaps between consecutive primes, and Iwaniec proved $Y(x) \ll x^2$.
Problem. Is $Y(x) \ll x^{1 + o(1)}$?
Source: Associated with E. Jacobsthal; P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), and Erdős problem #687. Listed as Problem 46 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- NT — Number Theory
- Secondary
- CO
- Keywords
- covering by residue classes, gaps between primes, Jacobsthal function, sieve theory
- Literature checked
- Nov. 3, 2026 by clemens-admin
References
@article{iwaniec1978jacobsthal,
author = {Iwaniec, Henryk},
title = {On the problem of {J}acobsthal},
journal = {Demonstratio Mathematica},
volume = {11},
number = {1},
pages = {225--232},
year = {1978},
doi = {10.1515/dema-1978-0121}
}
@article{fgkmt2018longgaps,
author = {Ford, Kevin and Green, Ben and Konyagin, Sergei and Maynard, James and Tao, Terence},
title = {Long gaps between primes},
journal = {Journal of the American Mathematical Society},
volume = {31},
number = {1},
pages = {65--105},
year = {2018},
doi = {10.1090/jams/876}
}
@misc{erdosproblems687,
author = {Bloom, Thomas F.},
title = {Erd{\H o}s {P}roblem \#687},
howpublished = {\url{https://www.erdosproblems.com/687}},
note = {Records the lower bound credited to GPT 5.6 Pro; see also problem \#4; accessed 2026-11-03},
year = {2026}
}
@misc{openai2026jacobsthal,
author = {{OpenAI}},
title = {A quadratic bound for {J}acobsthal's function},
howpublished = {\url{https://github.com/openai/math/blob/4eaee87548250b2682affda7d05d947c05554bae/preprints/A-quadratic-bound-for-Jacobsthals-function-September-25-2026/paper.pdf}},
note = {AI-generated, unrefereed; dated 25 September 2026},
year = {2026}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 46; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
Let $h(k)$ be the least integer such that every interval of $h(k)$ consecutive integers contains an integer coprime to any prescribed positive integer having at most $k$ distinct prime divisors. We prove $h(k)\ll k^2/(\log\log(3k))^2$, giving an affirmative answer to Jacobsthal's quadratic-bound question.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-11-08 | Open → Partially resolved | The registry's curators | A quadratic bound for Jacobsthal's function v1 recorded from math @ 4eaee87, build/main.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01136, "Jacobsthal's problem: covering an interval by one residue class per prime", clopen.solutions.