← All problems

Erdős Problem #970 — Runs containing integers coprime to sparse-prime numbers

For a positive integer nn, let ω(n)\omega(n) denote the number of its distinct prime divisors. For each integer k≥0k\geq 0, define h(k)h(k) to be the least positive integer mm such that for every positive integer nn with ω(n)≤k\omega(n)\leq k and every integer aa, at least one of a,a+1,…,a+m−1a,a+1,\ldots,a+m-1 is coprime to nn; equivalently,

h(k)=min⁡{m≥1: ∀n≥1 (ω(n)≤k) ∀a∈Z ∃j∈{0,…,m−1}, gcd⁡(a+j,n)=1}.h(k)=\min\left\{m\geq 1:\ \forall n\geq 1\ (\omega(n)\leq k)\ \forall a\in\mathbb Z\ \exists j\in\{0,\ldots,m-1\},\ \gcd(a+j,n)=1\right\}.

Determine the order of magnitude of h(k)h(k) as k→∞k\to\infty. In particular, does there exist an absolute constant CC such that h(k)≤Ck2h(k)\leq Ck^2 for all sufficiently large kk? Erdős Problems #970

Background

The problem is cited to Erdős’s 1965 account of recent advances and current problems in number theory. The proposed quadratic upper bound is Jacobsthal’s conjecture. In gap language, the function measures how long a run of consecutive integers can avoid being coprime to a modulus with at most kk distinct prime divisors; prime-power exponents do not affect that coprimality condition. A related sieve formulation asks how long an interval can be covered by choosing one residue class modulo each prime up to a fixed threshold. The Chinese remainder theorem connects such coverings to long runs of integers having a common prime factor with the resulting modulus. Erdős Problems #970 Erdős, Some recent advances and current problems in number theory (1965) Long gaps between primes (arXiv:1412.5029v3)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. The manuscript claims the uniform bound h(k) <= C k^2/(log log(3k))^2 with an absolute constant C for every integer k >= 1. This gives an affirmative answer to the quadratic-upper-bound question on this page for arbitrary prescribed sets of at most k distinct prime divisors and arbitrary interval translates; it does not determine the exact order of magnitude.See full solutionHide full solution

Claimed by OpenAI.

The manuscript claims the uniform bound h(k) <= C k^2/(log log(3k))^2 with an absolute constant C for every integer k >= 1. This gives an affirmative answer to the quadratic-upper-bound question on this page for arbitrary prescribed sets of at most k distinct prime divisors and arbitrary interval translates; it does not determine the exact order of magnitude.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-quadratic-bound-for-Jacobsthals-function-September-25-2026/paper.pdf

  • OpenAI-021-01-A-quadratic-bound-for-Jacobsthal-s-function.pdf824,106 bytesOpen