Problem 970

Let $h(k)$ be Jacobsthal's function, defined to as the minimal $m$ such that, if $n$ has at most $k$ prime factors, then in any set of $m$ consecutive integers there exists an integer coprime to $n$ . Determine the order of magnitude of $h(k)$ . In particular, is it true that

h(k) \ll k^2?

Source: erdosproblems.com/970

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open. The displayed question, $h(k)\ll k^2$ , is answered yes by the accepted partial claim of 25 September 2026 (the claim page (OpenAI, 2026)): the OpenAI release's Lean declaration OAI.Erdos970.Erdos970Final.erdos_970_quadratic, which states $h(k)\le Ck^2$ for one absolute $C$ and which this corpus built, axiom-checked and audited against the formulation above on 2026-10-07, the claim's only acceptance evidence. The manuscript claims the sharper $h(k)\ll k^2/(\log\log 3k)^2$ , which the release proves in a separate declaration, erdos_970_iterated_log, that this corpus has not axiom-checked or accepted; the manuscript has no refereed version and no outside review known here. The order of magnitude, to which the label attaches, stays open between the lower bounds below and the accepted quadratic bound. The bounds in hand from the search, whose scope the Current assessment records: the refereed upper bound $h(k)\ll(k\log k)^2$ (the claim page Iwaniec 1978, accepted, partial), 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, where $C(k)=h(k)-1$ is the same function as Erdős's 1965 $C(r)$ ([FGKMT18] attests the primorial case $Y(x)\ll x^2$ , and Erdős's 1965 lecture had $C(r)<c_2r^{c_3}$ ); and two lower bounds, Erdős's 1965 display (29), $C(r)>c_1r(\log r)^2\log_3r/(\log_2r)^2$ , and the bound obtained from [FGKMT18]'s (1.2) through the identity above, $h(k)\gg k(\log k)^2\log_3k/\log_2k$ , an authored one-line derivation recorded below and on the claim page Ford, Green, Konyagin, Maynard and Tao 2014 (accepted, partial). The site's commentary prints the best lower bound as $h(k)\gg k\log k\log_3k/(\log_2k)^2$ and attributes it to [FGKMT18]; that display is weaker than both source-supported bounds, by a factor of $\log k$ against (29) and $\log k\cdot\log_2k$ against the derived bound, is recorded here as the site's, with the discrepancy noted as a site-versus-source matter; it does not affect the label. Jacobsthal's conjecture $h(k)\ll k^2$ was already "hopeless at present" for Erdős in 1965. This is a bounded negative finding, not a certificate of openness.

Er65b: Erdős, P., Some recent advances and current problems in number theory. Lectures on Modern Mathematics, Vol. III, Wiley (1965), 196--244; the Jacobsthal passage with displays (29) and (30) on printed p. 208; display (13) on p. 201. Library home: Erdős 1965; result pages display (29) and display (30).
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)$ and the Jurkat--Richert bound on printed p. 225, the Theorem, the Corollary and Jacobsthal's questions on p. 226, and the note added in proof on p. 230. Library home: Iwaniec 1978; result pages Theorem and Corollary.
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; arXiv:1412.5029v3 (14 July 2016; the journal text not compared). Display (1.2), p. 3; (1.3) and the Iwaniec attestation, p. 4. Library home: Ford et al. 2018; result pages display (1.2) and Lemma 1.1 with (1.3).
Ja60: Jacobsthal, E., Über Sequenzen ganzer Zahlen, von denen keine zu $n$ teilerfremd ist, I--III. Norske Vid. Selsk. Forh. (Trondheim) 33 (1960), as OEIS A048669 cites it. Not held; the origin of the function and, per [Er65b], of the conjecture.
Er62: Erdős, P., On the integers relatively prime to $n$ and on a number theoretic function considered by Jacobsthal. Math. Scand. 10 (1962), 163--170 ([Er65b]'s reference [21]; DOI 10.7146/math.scand.a-10523 per OEIS A048669). Not held; context.
OEIS: Sequence A048669, The Jacobsthal function $g(n)$ : maximal gap in a list of all the integers relatively prime to $n$ (accessed 2026-09-18); its comments give the "least integer such that among any $g(n)$ consecutive integers there is at least one relatively prime to $n$ " form and Kanold's $g(n)\le2^w$ for $w$ distinct prime factors.

Problem 970

Status

Proof claims

Discussion