Erdős Problem #970 — Runs containing integers coprime to sparse-prime numbers
For a positive integer , let denote the number of its distinct prime divisors. For each integer , define to be the least positive integer such that for every positive integer with and every integer , at least one of is coprime to ; equivalently,
Determine the order of magnitude of as . In particular, does there exist an absolute constant such that for all sufficiently large ? 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 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
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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 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
- OpenAI-021-01-A-quadratic-bound-for-Jacobsthal-s-function.pdfOpen