Problem 860

Let $h(n)$ be such that, for any $m\geq 1$ , in the interval $(m,m+h(n))$ there exist distinct integers $a_i$ for $1\leq i\leq \pi(n)$ such that $p_i\mid a_i$ , where $p_i$ denotes the $i$ th prime.

Estimate $h(n)$ .

Source: erdosproblems.com/860

Number theory
Primes

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (page last edited 30 September 2025), with two pending partial claims on the proof-claims tab, neither of which would settle the problem; the Current assessment records them. The accepted partial claims are on the page of Erdős and Pomerance and Ruzsa's page; the Erdős--Selfridge lower bound and the joint upper bound of Chen and Korsky are claimed partial results, on the page of Erdős and Selfridge and the joint page of Chen and Korsky.

ErPo80: P. Erdős and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples in another interval. Indag. Math. (Proc.) 83 (1980), no. 2, 147--161, DOI 10.1016/1385-7258(80)90018-9. Library home: Erdős 1980.
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp. Section B32 "Grimm's conjecture", printed p. 133: "Erdős & Selfridge asked for an estimate of $f(n)$ ", the page's $h(n)$ less one, with the Erdős--Selfridge--Pomerance bounds $(3-\epsilon)n\le f(n)\ll n^{3/2}(\ln n)^{-1/2}$ for large $n$ . Library home: Guy 2004.

Problem 860

Status

Proof claims

Discussion