Erdős Problem #860

Erdős Problem 860 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/860.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT.

Let $p_1=2<p_2=3<p_3=5<\cdots$ be the primes in increasing order, and let $\pi(n)=|\{p\le n : p\text{ prime}\}|$.

Define $h(n)$ to be the least positive integer $L$ such that for every integer $m\ge 1$ there exist distinct integers \[ a_1,a_2,\dots,a_{\pi(n)}\in\mathbb Z \] with \[ m < a_i < m+L\quad\text{and}\quad p_i\mid a_i\quad\text{for each }i=1,2,\dots,\pi(n). \] (Thus the available integers are exactly $m+1, m+2,\dots,m+L-1$.)

The problem asks for estimates of $h(n)$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK.

The problem file records the following known results: Erdős--Pomerance proved $h(n)\ll n^{3/2}/\sqrt{\log n}$; Erdős--Selfridge proved $h(n)>(3-o(1))n$; Ruzsa proved $h(n)/n\to\infty$. We do not assume any additional literature.

ATTACK PLAN.

We prove a clean elementary lower bound using gaps between multiples of the largest prime $\le n$, and a clean elementary upper bound by a greedy "choose an unused multiple" procedure. We also compute exact $h(n)$ for $n\le 10$ to sanity-check.

WORK.

Lemma 860.1 (Lower bound from gaps between multiples).

Lemma. Let $q$ be the largest prime $\le n$ (so $q=p_{\pi(n)}$). Then $h(n)\ge q+1$.

Proof. Fix $m$ to be a multiple of $q$, say $m=q\ell$. The integers strictly between $m$ and $m+q$ are $m+1,m+2,\dots,m+q-1$; none of these are divisible by $q$ because the next multiple of $q$ after $m$ is $m+q$, which is not included in the open interval $(m,m+q)$.

Therefore, if $L\le q$, then the interval $(m,m+L)$ contains no integer divisible by $q$, so it is impossible to choose $a_{\pi(n)}$ with $q\mid a_{\pi(n)}$. Thus any $L$ that works for all $m$ must satisfy $L\ge q+1$. $\square$

Lemma 860.2 (A greedy upper bound).

Lemma. For every $n\ge 2$, \[ h(n) \le n\,\pi(n) + 1. \]

Proof. Let $L:=n\pi(n)+1$. Fix an arbitrary integer $m\ge 1$. We construct the required distinct integers $a_1,\dots,a_{\pi(n)}$ inductively.

Suppose $1\le i\le \pi(n)$ and we have already chosen distinct integers $a_1,\dots,a_{i-1}$ with \[ m<a_j<m+L\quad\text{and}\quad p_j\mid a_j\quad\text{for }1\le j<i. \] Consider the first $i$ multiples of $p_i$ that are strictly larger than $m$. These are \[ b_r := p_i\left(\lfloor \frac{m}{p_i}\rfloor + r\right)\qquad (r=1,2,\dots,i). \] Each $b_r$ is divisible by $p_i$ and satisfies $m < b_r \le m + r p_i \le m + i p_i$. Since $p_i\le n$ and $i\le \pi(n)$, we have $i p_i \le \pi(n) n = L-1$, hence $b_r < m+L$. So all $b_1,\dots,b_i$ lie in the allowed interval $(m,m+L)$.

Among the $i$ candidates $b_1,\dots,b_i$, at most $i-1$ can coincide with the previously chosen $a_1,\dots,a_{i-1}$, because the $a_j$ are distinct. Therefore there exists at least one $r\in\{1,\dots,i\}$ such that $b_r\notin\{a_1,\dots,a_{i-1}\}$. Choose $a_i:=b_r$ for such an $r$. Then $a_i$ is divisible by $p_i$, lies in $(m,m+L)$, and is distinct from $a_1,\dots,a_{i-1}$.

Proceeding inductively constructs distinct $a_1,\dots,a_{\pi(n)}$ in $(m,m+L)$ with $p_i\mid a_i$ for each $i$. Since $m$ was arbitrary, $L$ works for all $m$, hence $h(n)\le L = n\pi(n)+1$. $\square$

Fast reality check (exact $h(n)$ for $n\le 10$).

For $n\le 10$ (so the relevant primes are $\{2\}$, $\{2,3\}$, $\{2,3,5\}$, or $\{2,3,5,7\}$), the pattern of divisibility in intervals is periodic modulo $P=\prod_{p\le n} p$. Brute-force checking all $m\bmod P$ and solving the matching problem for each $m$ gives: \[ \begin{array}{c|ccccccccc} n & 2&3&4&5&6&7&8&9&10\\\hline h(n) & 3&5&5&7&7&11&11&11&11 \end{array} \]

VERIFICATION.

• Lemma 860.1 uses only the fact that multiples of $q$ occur exactly every $q$ integers, and the open-interval endpoint exclusion.
• Lemma 860.2 carefully accounts for the open interval: we ensured $b_r\le m+(L-1)$, hence $b_r<m+L$.
• For $n=2$, Lemma 860.1 gives $h(2)\ge 3$ and Lemma 860.2 gives $h(2)\le 3$; the computed value is $h(2)=3$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved the explicit lower bound $h(n)\ge p_{\pi(n)}+1$ and the explicit upper bound $h(n)\le n\pi(n)+1$. We also computed exact values of $h(n)$ for $n\le 10$.

(ii) First gap. Sharpen the growth rate of $h(n)$: even determining the correct order of magnitude between $n\pi(n)$ and the much smaller $n^{3/2}/\sqrt{\log n}$ recorded in the problem file is open here.

(iii) Top 3 next moves. $1$ Replace the greedy argument by a Hall-type expansion argument for the bipartite graph between primes $p\le n$ and integers in $(m,m+L)$, to reduce $L$. $2$ Search computationally for the worst-case $m$ for moderate $n$ (say $n\le 30$) and attempt to guess the asymptotic constant factors. $3$ Construct explicit "obstruction intervals" forcing large $h(n)$ by packing many primes' multiples into the same integers (high overlap), to strengthen lower bounds.

(iv) What a minimal counterexample would look like. A minimal obstruction to a smaller $h(n)$ would be an interval where the set of available multiples of the primes $\le n$ has large overlaps, so that any attempt to pick distinct representatives forces leaving some prime unmatched; such intervals likely have many integers with unusually many small prime factors.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.

Let $p_1=2<p_2=3<p_3=5<\cdots$ be the primes in increasing order, and let $\pi(n)=|\{p\le n : p\text{ prime}\}|$.

Define $h(n)$ to be the least positive integer $L$ such that for every integer $m\ge 1$ there exist distinct integers \[ a_1,a_2,\dots,a_{\pi(n)}\in\mathbb Z \] with \[ m < a_i < m+L\quad\text{and}\quad p_i\mid a_i\quad\text{for each }i=1,2,\dots,\pi(n). \] (Thus the available integers are exactly $m+1, m+2,\dots,m+L-1$.)

The problem asks for estimates of $h(n)$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK.

The problem file records the following known results: Erdős--Pomerance proved $h(n)\ll n^{3/2}/\sqrt{\log n}$; Erdős--Selfridge proved $h(n)>(3-o(1))n$; Ruzsa proved $h(n)/n\to\infty$. We do not assume any additional literature.

ATTACK PLAN.

We prove a clean elementary lower bound using gaps between multiples of the largest prime $\le n$, and a clean elementary upper bound by a greedy "choose an unused multiple" procedure. We also compute exact $h(n)$ for $n\le 10$ to sanity-check.

WORK.

Lemma 860.1 (Lower bound from gaps between multiples).

Lemma. Let $q$ be the largest prime $\le n$ (so $q=p_{\pi(n)}$). Then $h(n)\ge q+1$.

Proof. Fix $m$ to be a multiple of $q$, say $m=q\ell$. The integers strictly between $m$ and $m+q$ are $m+1,m+2,\dots,m+q-1$; none of these are divisible by $q$ because the next multiple of $q$ after $m$ is $m+q$, which is not included in the open interval $(m,m+q)$.

Therefore, if $L\le q$, then the interval $(m,m+L)$ contains no integer divisible by $q$, so it is impossible to choose $a_{\pi(n)}$ with $q\mid a_{\pi(n)}$. Thus any $L$ that works for all $m$ must satisfy $L\ge q+1$. $\square$

Lemma 860.2 (A greedy upper bound).

Lemma. For every $n\ge 2$, \[ h(n) \le n\,\pi(n) + 1. \]

Proof. Let $L:=n\pi(n)+1$. Fix an arbitrary integer $m\ge 1$. We construct the required distinct integers $a_1,\dots,a_{\pi(n)}$ inductively.

Suppose $1\le i\le \pi(n)$ and we have already chosen distinct integers $a_1,\dots,a_{i-1}$ with \[ m<a_j<m+L\quad\text{and}\quad p_j\mid a_j\quad\text{for }1\le j<i. \] Consider the first $i$ multiples of $p_i$ that are strictly larger than $m$. These are \[ b_r := p_i\left(\lfloor \frac{m}{p_i}\rfloor + r\right)\qquad (r=1,2,\dots,i). \] Each $b_r$ is divisible by $p_i$ and satisfies $m < b_r \le m + r p_i \le m + i p_i$. Since $p_i\le n$ and $i\le \pi(n)$, we have $i p_i \le \pi(n) n = L-1$, hence $b_r < m+L$. So all $b_1,\dots,b_i$ lie in the allowed interval $(m,m+L)$.

Among the $i$ candidates $b_1,\dots,b_i$, at most $i-1$ can coincide with the previously chosen $a_1,\dots,a_{i-1}$, because the $a_j$ are distinct. Therefore there exists at least one $r\in\{1,\dots,i\}$ such that $b_r\notin\{a_1,\dots,a_{i-1}\}$. Choose $a_i:=b_r$ for such an $r$. Then $a_i$ is divisible by $p_i$, lies in $(m,m+L)$, and is distinct from $a_1,\dots,a_{i-1}$.

Proceeding inductively constructs distinct $a_1,\dots,a_{\pi(n)}$ in $(m,m+L)$ with $p_i\mid a_i$ for each $i$. Since $m$ was arbitrary, $L$ works for all $m$, hence $h(n)\le L = n\pi(n)+1$. $\square$

Fast reality check (exact $h(n)$ for $n\le 10$).

For $n\le 10$ (so the relevant primes are $\{2\}$, $\{2,3\}$, $\{2,3,5\}$, or $\{2,3,5,7\}$), the pattern of divisibility in intervals is periodic modulo $P=\prod_{p\le n} p$. Brute-force checking all $m\bmod P$ and solving the matching problem for each $m$ gives: \[ \begin{array}{c|ccccccccc} n & 2&3&4&5&6&7&8&9&10\\\hline h(n) & 3&5&5&7&7&11&11&11&11 \end{array} \]

VERIFICATION.

• Lemma 860.1 uses only the fact that multiples of $q$ occur exactly every $q$ integers, and the open-interval endpoint exclusion.
• Lemma 860.2 carefully accounts for the open interval: we ensured $b_r\le m+(L-1)$, hence $b_r<m+L$.
• For $n=2$, Lemma 860.1 gives $h(2)\ge 3$ and Lemma 860.2 gives $h(2)\le 3$; the computed value is $h(2)=3$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved the explicit lower bound $h(n)\ge p_{\pi(n)}+1$ and the explicit upper bound $h(n)\le n\pi(n)+1$. We also computed exact values of $h(n)$ for $n\le 10$.

(ii) First gap. Sharpen the growth rate of $h(n)$: even determining the correct order of magnitude between $n\pi(n)$ and the much smaller $n^{3/2}/\sqrt{\log n}$ recorded in the problem file is open here.

(iii) Top 3 next moves. $1$ Replace the greedy argument by a Hall-type expansion argument for the bipartite graph between primes $p\le n$ and integers in $(m,m+L)$, to reduce $L$. $2$ Search computationally for the worst-case $m$ for moderate $n$ (say $n\le 30$) and attempt to guess the asymptotic constant factors. $3$ Construct explicit "obstruction intervals" forcing large $h(n)$ by packing many primes' multiples into the same integers (high overlap), to strengthen lower bounds.

(iv) What a minimal counterexample would look like. A minimal obstruction to a smaller $h(n)$ would be an interval where the set of available multiples of the primes $\le n$ has large overlaps, so that any attempt to pick distinct representatives forces leaving some prime unmatched; such intervals likely have many integers with unusually many small prime factors.