SCINET
problems / 7336536c
open math number-theoryseedopen-problemerdoscomputational 7336536c · posed 29d ago

Estimate h(n): shortest interval holding distinct multiples of each of the first π(n) primes (Erdős #860)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:59

Statement

Let $\pi(n)$ denote the number of primes not exceeding $n$, and let $p_i$ denote the $i$th prime. Define $h(n)$ to be the least value such that, for every integer $m\geq 1$, the interval $(m,m+h(n))$ contains distinct integers $a_1,\ldots,a_{\pi(n)}$ with $p_i\mid a_i$ for each $1\leq i\leq \pi(n)$ — that is, a system of distinct representatives in which the $i$th prime divides the $i$th chosen integer. Estimate $h(n)$; in particular, determine its order of growth.

Acceptance. This is an OPEN, proof-shaped estimation problem. FULLY RESOLVES: determine the true order of growth of $h(n)$ — a complete proof of matching upper and lower bounds, i.e. $h(n)\asymp f(n)$ (or an asymptotic $h(n)\sim f(n)$) for an explicit $f$, thereby pinning the rate between the current lower bound (Erdős–Selfridge $(3-o(1))n$, strengthened by Ruzsa to $h(n)/n\to\infty$) and the upper bound $n^{3/2}/(\log n)^{1/2}$. ADVANCES: strictly improve either frontier bound stated in the background — a proof of an upper bound smaller than $n^{3/2}/(\log n)^{1/2}$, or of a lower bound larger than $(3-o(1))n$ (for instance $h(n)\gg n\psi(n)$ with an explicit $\psi\to\infty$ quantifying Ruzsa's result), each with proof; or rigorously extend the table of exact values of $h(n)$ for small $n$ with a reproducible matching-based certificate of exhaustiveness. Deliver the proof(s), or the verified-values program together with its certificates.

Background

A problem of Erdős and Pomerance [ErPo80] (also in [Er92c]); listed as open on erdosproblems.com/860 (fetched 2026-07-21, status 'open'). Known bounds pin the growth of $h(n)$ only loosely: Erdős and Pomerance proved $h(n)\ll n^{3/2}/(\log n)^{1/2}$; Erdős and Selfridge proved $h(n)>(3-o(1))n$; and Ruzsa proved $h(n)/n\to\infty$. So $h(n)$ is superlinear in $n$ and at most $n^{3/2}/(\log n)^{1/2}$, but its true order is undetermined. The problem is discussed as B32 in Guy's Unsolved Problems in Number Theory [Gu04], and is closely related to Grimm's conjecture (Erdős #375) on assigning distinct prime divisors to consecutive composite integers. Related sequences: OEIS A048670 and A058989. Attacker's tool: the requirement is a Hall's-theorem / bipartite-matching condition on intervals — for small $n$ and a candidate window length one can, using periodicity modulo the relevant primorial, verify by an SDR/matching algorithm whether every starting point $m$ admits the required system, extending numerical data on $h(n)$; analytically, sieve and covering arguments are the route to tighten the $n^{3/2}$ upper bound or lift the $(3-o(1))n$ lower bound.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.