Erdős Problem #710

Erdős Problem 710 --- 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/710.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

For each $n\ge 1$, let $f(n)$ be the minimal real number such that there exist distinct integers \[ a_1,a_2,\dots,a_n\in (n,\,n+f(n)) \] with the divisibility constraints \[ k\mid a_k\qquad\text{for all }1\le k\le n. \] (There is a mild ambiguity about whether $f(n)$ is required to be an integer and about the open interval endpoints; in the computations below I interpret $f(n)$ as the minimal integer such that the open interval $(n,n+f(n))$ contains a feasible set.)

2) QUICK LITERATURE/CONTEXT CHECK

Using only what is stated in the problem text: Erdős--Pomerance proved \[ (2/\sqrt{e}+o(1))n\left(\frac{\log n}{\log\log n}\right)^{1/2}\le f(n)\le (1.7398\cdots+o(1))n(\log n)^{1/2}. \]

3) ATTACK PLAN

- Prove elementary lower bounds from the need to include a multiple of $n$. - Prove elementary upper bounds by explicit constructions (very non-optimal). - Compute small-$n$ exact values (in the integer/open-interval interpretation) as a sanity check.

4) WORK

Lemma 710.1 (Basic lower bound $f(n)>n$; hence $f(n)\ge n+1$ if $f(n)$ is integral). For any $n\ge 1$, any feasible $a_n$ must satisfy $a_n\ge 2n$. Consequently, if the feasible interval is $(n,n+f(n))$, then necessarily $n+f(n)>2n$, i.e. $f(n)>n$.

Proof. Because $n\mid a_n$ and $a_n>n$ (since $a_n\in(n,n+f(n))$), the smallest possible value of $a_n$ is the least multiple of $n$ strictly exceeding $n$, namely $2n$. Thus any feasible solution requires $(n,n+f(n))$ to contain at least one multiple of $n$, hence must extend beyond $2n$. Formally, if $n+f(n)\le 2n$ then $(n,n+f(n))\subseteq(n,2n]$ contains no multiple of $n$, contradiction. Therefore $f(n)>n$. $\square$

Lemma 710.2 (Crude explicit upper bound $f(n)\le n(n+1)$). For every $n\ge 1$, there exist distinct integers $a_1,\dots,a_n$ with $k\mid a_k$ and \[ a_k\in (n,\,n+n(n+1))\quad\text{for all }k, \] so in particular $f(n)\le n(n+1)$.

Proof. Set \[ a_k := k(n+1),\qquad 1\le k\le n. \] Then $k\mid a_k$ is immediate. The values are distinct because $k\mapsto k(n+1)$ is injective. Moreover, since $k\ge 1$ and $n\ge 1$, we have $a_k\ge n+1>n$. Also $a_k\le n(n+1)$, hence $a_k < n + n(n+1)$. Thus $a_k\in(n,\,n+n(n+1))$ for every $k$. Therefore a feasible set exists in that interval, proving $f(n)\le n(n+1)$. $\square$

FAST REALITY CHECK (exact small $n$ in the integer/open-interval model). I computed (by Hopcroft--Karp bipartite matching) the minimal integer $f(n)$ such that there exist distinct integers $a_k\in(n,n+f(n))$ with $k\mid a_k$. Results for $1\le n\le 20$:

 n :  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
 f :  2  3  4  6  6  9  9 11 13 15 15 17 16 19 20 25 24 27 26 29

5) VERIFICATION

- Lemma 710.1: checks the first available multiple of $n$ above $n$ is $2n$; correct. - Lemma 710.2: divisibility and distinctness are immediate; interval containment checked by bounding $a_k$ between $n+1$ and $n(n+1)$. - Computation: The matching formulation is: left nodes $k=1,\dots,n$, right nodes integers $x\in\{n+1,\dots,n+f(n)-1\}$ (since the interval is open), with edges when $k\mid x$. A perfect matching gives the desired distinct multiples.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I proved elementary bounds $f(n)>n$ (Lemma 710.1) and $f(n)\le n(n+1)$ (Lemma 710.2), and computed exact small values for $n\le 20$ in the integer/open-interval interpretation.

(ii) First gap (crisp). Determine the true asymptotic growth of $f(n)$ (beyond the stated bounds in the problem text), i.e. find constants/functions $g(n)$ with $f(n)\sim g(n)$.

(iii) Top 3 next moves. 1. Try to sharpen the constructive upper bound by a greedy or matching-based algorithm that keeps $a_k$ near $2n$ while avoiding collisions. 2. For lower bounds, analyze the scarcity of numbers with large prime factors in short intervals: large $k$ force use of relatively rare multiples. 3. Extend computation to larger $n$ to guess the correct asymptotic scale (e.g. whether $f(n)/\left(n\sqrt{\log n}\right)$ stabilizes).

(iv) Minimal counterexample structure. A minimal counterexample to a proposed upper bound $f(n)\le U(n)$ would be an $n$ such that the bipartite graph between $\{1,\dots,n\}$ and $(n,n+U(n))\cap\mathbb{Z}$ (edges given by divisibility) has no matching covering the left side; by Hall's theorem, there must exist a subset $S\subseteq\{1,\dots,n\}$ for which the set of multiples of elements of $S$ in the interval has size $<|S|$.

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.

1) FORMAL RESTATEMENT

For each $n\ge 1$, let $f(n)$ be the minimal real number such that there exist distinct integers \[ a_1,a_2,\dots,a_n\in (n,\,n+f(n)) \] with the divisibility constraints \[ k\mid a_k\qquad\text{for all }1\le k\le n. \] (There is a mild ambiguity about whether $f(n)$ is required to be an integer and about the open interval endpoints; in the computations below I interpret $f(n)$ as the minimal integer such that the open interval $(n,n+f(n))$ contains a feasible set.)

2) QUICK LITERATURE/CONTEXT CHECK

Using only what is stated in the problem text: Erdős--Pomerance proved \[ (2/\sqrt{e}+o(1))n\left(\frac{\log n}{\log\log n}\right)^{1/2}\le f(n)\le (1.7398\cdots+o(1))n(\log n)^{1/2}. \]

3) ATTACK PLAN

- Prove elementary lower bounds from the need to include a multiple of $n$. - Prove elementary upper bounds by explicit constructions (very non-optimal). - Compute small-$n$ exact values (in the integer/open-interval interpretation) as a sanity check.

4) WORK

Lemma 710.1 (Basic lower bound $f(n)>n$; hence $f(n)\ge n+1$ if $f(n)$ is integral). For any $n\ge 1$, any feasible $a_n$ must satisfy $a_n\ge 2n$. Consequently, if the feasible interval is $(n,n+f(n))$, then necessarily $n+f(n)>2n$, i.e. $f(n)>n$.

Proof. Because $n\mid a_n$ and $a_n>n$ (since $a_n\in(n,n+f(n))$), the smallest possible value of $a_n$ is the least multiple of $n$ strictly exceeding $n$, namely $2n$. Thus any feasible solution requires $(n,n+f(n))$ to contain at least one multiple of $n$, hence must extend beyond $2n$. Formally, if $n+f(n)\le 2n$ then $(n,n+f(n))\subseteq(n,2n]$ contains no multiple of $n$, contradiction. Therefore $f(n)>n$. $\square$

Lemma 710.2 (Crude explicit upper bound $f(n)\le n(n+1)$). For every $n\ge 1$, there exist distinct integers $a_1,\dots,a_n$ with $k\mid a_k$ and \[ a_k\in (n,\,n+n(n+1))\quad\text{for all }k, \] so in particular $f(n)\le n(n+1)$.

Proof. Set \[ a_k := k(n+1),\qquad 1\le k\le n. \] Then $k\mid a_k$ is immediate. The values are distinct because $k\mapsto k(n+1)$ is injective. Moreover, since $k\ge 1$ and $n\ge 1$, we have $a_k\ge n+1>n$. Also $a_k\le n(n+1)$, hence $a_k < n + n(n+1)$. Thus $a_k\in(n,\,n+n(n+1))$ for every $k$. Therefore a feasible set exists in that interval, proving $f(n)\le n(n+1)$. $\square$

FAST REALITY CHECK (exact small $n$ in the integer/open-interval model). I computed (by Hopcroft--Karp bipartite matching) the minimal integer $f(n)$ such that there exist distinct integers $a_k\in(n,n+f(n))$ with $k\mid a_k$. Results for $1\le n\le 20$:

 n :  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
 f :  2  3  4  6  6  9  9 11 13 15 15 17 16 19 20 25 24 27 26 29

5) VERIFICATION

- Lemma 710.1: checks the first available multiple of $n$ above $n$ is $2n$; correct. - Lemma 710.2: divisibility and distinctness are immediate; interval containment checked by bounding $a_k$ between $n+1$ and $n(n+1)$. - Computation: The matching formulation is: left nodes $k=1,\dots,n$, right nodes integers $x\in\{n+1,\dots,n+f(n)-1\}$ (since the interval is open), with edges when $k\mid x$. A perfect matching gives the desired distinct multiples.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. I proved elementary bounds $f(n)>n$ (Lemma 710.1) and $f(n)\le n(n+1)$ (Lemma 710.2), and computed exact small values for $n\le 20$ in the integer/open-interval interpretation.

(ii) First gap (crisp). Determine the true asymptotic growth of $f(n)$ (beyond the stated bounds in the problem text), i.e. find constants/functions $g(n)$ with $f(n)\sim g(n)$.

(iii) Top 3 next moves. 1. Try to sharpen the constructive upper bound by a greedy or matching-based algorithm that keeps $a_k$ near $2n$ while avoiding collisions. 2. For lower bounds, analyze the scarcity of numbers with large prime factors in short intervals: large $k$ force use of relatively rare multiples. 3. Extend computation to larger $n$ to guess the correct asymptotic scale (e.g. whether $f(n)/\left(n\sqrt{\log n}\right)$ stabilizes).

(iv) Minimal counterexample structure. A minimal counterexample to a proposed upper bound $f(n)\le U(n)$ would be an $n$ such that the bipartite graph between $\{1,\dots,n\}$ and $(n,n+U(n))\cap\mathbb{Z}$ (edges given by divisibility) has no matching covering the left side; by Hall's theorem, there must exist a subset $S\subseteq\{1,\dots,n\}$ for which the set of multiples of elements of $S$ in the interval has size $<|S|$.