Erdős Problem #463

Erdős Problem 463 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/463

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/463.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/463.tex.

1) FORMAL RESTATEMENT.

Let $p(m)$ denote the least prime factor of $m$ (for $m\ge 2$), and interpret the quantifier "$m$ is composite" as part of the condition (otherwise the auxiliary quantity $F(n)=\min_{m>n}(m-p(m))$ would be identically $0$ because primes have $p(m)=m$).

Question: Does there exist a function $f:\mathbb{N}\to\mathbb{N}$ with $f(n)\to\infty$ such that for all sufficiently large integers $n$ there exists a composite integer $m$ satisfying \[ n+f(n)<m<n+p(m)? \] Equivalently, writing $m=n+k$, we ask whether for all large $n$ there exists an integer $k>f(n)$ such that $n+k$ is composite and $p(n+k)>k$.

In terms of $F(n):=\min\{m-p(m): m>n\ \text{composite}\}$, the existence of such an $f$ is equivalent to the statement that $n-F(n)\to\infty$ (since $m<n+p(m)\iff m-p(m)<n$).

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement cites Erdős' question in [Er92e] about whether $n-F(n)\sim c\,n^{1/2}$ for some $c>0$. I will not use any results beyond what is explicitly stated in the problem text.

3) ATTACK PLAN.

• Rephrase the inequality in terms of a shift $k=m-n$ and the roughness condition $p(n+k)>k$.
• Prove unconditional structural bounds on any such $k$ (in particular, show $k\ll \sqrt{n}$ always).
• Exhibit an explicit infinite family of $n$ for which a solution exists with $k\asymp \sqrt{n}$ (prime squares).
• Run an exact brute-force check for small $n$ using the structural bound on $k$.

4) WORK.

Lemma 463.1 (shift/roughness equivalence). For an integer $n\ge 1$ and an integer $k\ge 1$, set $m=n+k$. Then \[ n<m<n+p(m)\quad\Longleftrightarrow\quad k<p(n+k). \] Consequently, the original problem is equivalent to: find $f(n)\to\infty$ such that for all large $n$ there exists an integer $k>f(n)$ with $n+k$ composite and $p(n+k)>k$.

Proof. The inequalities $n<m$ and $m<n+p(m)$ are respectively $k>0$ and $n+k<n+p(n+k)$, i.e. $k<p(n+k)$. Conversely, $k<p(n+k)$ implies $n<n+k<n+p(n+k)$. $\square$

Lemma 463.2 (prime-square intervals give $k\asymp\sqrt{n}$ infinitely often). Let $p$ be prime and let $n$ be any integer with \[ p^2-p<n<p^2. \] Then taking $m=p^2$ (composite) yields \[ n<m<n+p(m). \] In particular, for $n=p^2-p+1$ we obtain a valid shift $k=m-n=p-1\asymp \sqrt{n}$.

Proof. Let $m=p^2$. Then $p(m)=p$ and $m-n=p^2-n=:k$ satisfies $1\le k\le p-1$ because $p^2-p<n<p^2$. Hence $k<p=p(m)$, i.e. $m<n+p(m)$, and clearly $m>n$. $\square$

Lemma 463.3 (universal upper bound $k\ll\sqrt{n}$). Suppose $m=n+k$ is composite and satisfies $k<p(m)$. Then \[ k^2+k\le n. \] Equivalently, \[ k\le \left\lfloor\frac{\sqrt{4n+1}-1}{2}\right\rfloor<\sqrt{n}. \]

Proof. Since $k<p(m)$ and both are integers, $p(m)\ge k+1$. As $m$ is composite and $p(m)$ is its least prime factor, we can write $m=p(m)\cdot r$ with $r\ge p(m)$, hence $m\ge p(m)^2\ge (k+1)^2$. Using $m=n+k$ gives $n+k\ge (k+1)^2=k^2+2k+1$, i.e. $n\ge k^2+k+1$, hence $k^2+k\le n-1<n$ and in particular $k^2+k\le n$. $\square$

FAST REALITY CHECK (exact for small $n$). Define \[ h(n):=\max\{k\ge 1: n+k\ \text{composite and }\ p(n+k)>k\} \] (with $h(n)=\text{None}$ if no such $k$ exists). By Lemma 463.3 it suffices to test $1\le k\le \lfloor(\sqrt{4n+1}-1)/2\rfloor$.

A brute-force script checked $h(n)$ for $2\le n\le 50$ and produced the following (format: $n$, $h(n)$, witness $(m,p(m))$, and the tested bound $k_{\max}$):

 n h(n) witness(m,p) kmax
 2 None         None    1
 3    1       (4, 2)    1
 4 None         None    1
 5    1       (6, 2)    1
 6 None         None    2
 7    2       (9, 3)    2
 8    1       (9, 3)    2
 9    1      (10, 2)    2
10 None         None    2
11    1      (12, 2)    2
12 None         None    3
13    2      (15, 3)    3
14    1      (15, 3)    3
15    1      (16, 2)    3
16 None         None    3
17    1      (18, 2)    3
18 None         None    3
19    2      (21, 3)    3
20    1      (21, 3)    4
21    4      (25, 5)    4
22    3      (25, 5)    4
23    2      (25, 5)    4
24    1      (25, 5)    4
25    2      (27, 3)    4
26    1      (27, 3)    4
27    1      (28, 2)    4
28 None         None    4
29    1      (30, 2)    4
30 None         None    5
31    4      (35, 5)    5
32    3      (35, 5)    5
33    2      (35, 5)    5
34    1      (35, 5)    5
35    1      (36, 2)    5
36 None         None    5
37    2      (39, 3)    5
38    1      (39, 3)    5
39    1      (40, 2)    5
40 None         None    5
41    1      (42, 2)    5
42 None         None    6
43    6      (49, 7)    6
44    5      (49, 7)    6
45    4      (49, 7)    6
46    3      (49, 7)    6
47    2      (49, 7)    6
48    1      (49, 7)    6
49    2      (51, 3)    6
50    1      (51, 3)    6

In particular, one sees the prime-square phenomenon: for $n\in\{43,44,45,46,47,48\}$ the witness is $m=49=7^2$ and the gap $k=49-n$ ranges from $6$ down to $1$.

For $n\le 500$, the ten largest values found were:

(bestk, n, (m,p(m)))
(18, 419, (437, 19))
(18, 343, (361, 19))
(17, 420, (437, 19))
(17, 344, (361, 19))
(16, 477, (493, 17))
(16, 421, (437, 19))
(16, 375, (391, 17))
(16, 345, (361, 19))
(16, 307, (323, 17))
(16, 273, (289, 17))

All of these correspond to witnesses $m=p^2$ with $p\in\{17,19\}$.

5) VERIFICATION.

• Lemma 463.3 uses only the inequality $m\ge p(m)^2$ (true for composite $m$) and the integer step $p(m)\ge k+1$ when $k<p(m)$.
• The brute-force check is exact for each tested $n$ because Lemma 463.3 reduces the search to finitely many $k$.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result. Unconditionally, any admissible gap $k=m-n$ must satisfy $k^2+k\le n$ (Lemma 463.3), so $k=O(\sqrt{n})$. Conversely, for infinitely many $n$ (namely $p^2-p<n<p^2$ with $p$ prime) the choice $m=p^2$ gives a solution with $k$ as large as $p-1\asymp\sqrt{n}$ (Lemma 463.2). Computations up to $n\le 500$ match this prime-square behavior.

(ii) First gap (crisp). Prove (or disprove) that $h(n):=\max\{k: n+k\text{ composite and }p(n+k)>k\}$ satisfies $h(n)\to\infty$ as $n\to\infty$. Equivalently: produce an explicit $f(n)\to\infty$ such that for every sufficiently large $n$ there exists a composite $m=n+k$ with $k>f(n)$ and $p(m)>k$.

(iii) Top 3 next moves.

1. Develop a sieve-theoretic lower bound for the existence of a $k$-rough composite in the short interval $(n+g(n),\,n+\lfloor(\sqrt{4n+1}-1)/2\rfloor]$ for some $g(n)\to\infty$.
2. Try a structured construction beyond prime squares: e.g. semiprimes $m=pq$ with $p\approx q\approx \sqrt{n}$, aiming to force $p(m)=p>m-n$.
3. Computation: for each $n$ search all $k$ up to the exact bound in Lemma 463.3 and study the distribution of $h(n)$ (especially the frequency of $h(n)=\text{None}$) to guess the true order of $\min_{n\le x} h(n)$.

(iv) Minimal counterexample structure. A counterexample to the existence of such an $f$ would require infinitely many large $n$ for which every $k$ in a long initial range (say $1\le k\le K(n)$ with $K(n)\to\infty$) fails: for each such $k$, either $n+k$ is prime or else $p(n+k)\le k$. Any "minimal" obstruction would thus be an $n$ for which all composites in $[n+1,\,n+K(n)]$ have unusually small least prime factor relative to their distance from $n$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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.

Let $p(m)$ denote the least prime factor of $m$ (for $m\ge 2$), and interpret the quantifier "$m$ is composite" as part of the condition (otherwise the auxiliary quantity $F(n)=\min_{m>n}(m-p(m))$ would be identically $0$ because primes have $p(m)=m$).

Question: Does there exist a function $f:\mathbb{N}\to\mathbb{N}$ with $f(n)\to\infty$ such that for all sufficiently large integers $n$ there exists a composite integer $m$ satisfying \[ n+f(n)<m<n+p(m)? \] Equivalently, writing $m=n+k$, we ask whether for all large $n$ there exists an integer $k>f(n)$ such that $n+k$ is composite and $p(n+k)>k$.

In terms of $F(n):=\min\{m-p(m): m>n\ \text{composite}\}$, the existence of such an $f$ is equivalent to the statement that $n-F(n)\to\infty$ (since $m<n+p(m)\iff m-p(m)<n$).

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement cites Erdős' question in [Er92e] about whether $n-F(n)\sim c\,n^{1/2}$ for some $c>0$. I will not use any results beyond what is explicitly stated in the problem text.

3) ATTACK PLAN.

• Rephrase the inequality in terms of a shift $k=m-n$ and the roughness condition $p(n+k)>k$.
• Prove unconditional structural bounds on any such $k$ (in particular, show $k\ll \sqrt{n}$ always).
• Exhibit an explicit infinite family of $n$ for which a solution exists with $k\asymp \sqrt{n}$ (prime squares).
• Run an exact brute-force check for small $n$ using the structural bound on $k$.

4) WORK.

Lemma 463.1 (shift/roughness equivalence). For an integer $n\ge 1$ and an integer $k\ge 1$, set $m=n+k$. Then \[ n<m<n+p(m)\quad\Longleftrightarrow\quad k<p(n+k). \] Consequently, the original problem is equivalent to: find $f(n)\to\infty$ such that for all large $n$ there exists an integer $k>f(n)$ with $n+k$ composite and $p(n+k)>k$.

Proof. The inequalities $n<m$ and $m<n+p(m)$ are respectively $k>0$ and $n+k<n+p(n+k)$, i.e. $k<p(n+k)$. Conversely, $k<p(n+k)$ implies $n<n+k<n+p(n+k)$. $\square$

Lemma 463.2 (prime-square intervals give $k\asymp\sqrt{n}$ infinitely often). Let $p$ be prime and let $n$ be any integer with \[ p^2-p<n<p^2. \] Then taking $m=p^2$ (composite) yields \[ n<m<n+p(m). \] In particular, for $n=p^2-p+1$ we obtain a valid shift $k=m-n=p-1\asymp \sqrt{n}$.

Proof. Let $m=p^2$. Then $p(m)=p$ and $m-n=p^2-n=:k$ satisfies $1\le k\le p-1$ because $p^2-p<n<p^2$. Hence $k<p=p(m)$, i.e. $m<n+p(m)$, and clearly $m>n$. $\square$

Lemma 463.3 (universal upper bound $k\ll\sqrt{n}$). Suppose $m=n+k$ is composite and satisfies $k<p(m)$. Then \[ k^2+k\le n. \] Equivalently, \[ k\le \left\lfloor\frac{\sqrt{4n+1}-1}{2}\right\rfloor<\sqrt{n}. \]

Proof. Since $k<p(m)$ and both are integers, $p(m)\ge k+1$. As $m$ is composite and $p(m)$ is its least prime factor, we can write $m=p(m)\cdot r$ with $r\ge p(m)$, hence $m\ge p(m)^2\ge (k+1)^2$. Using $m=n+k$ gives $n+k\ge (k+1)^2=k^2+2k+1$, i.e. $n\ge k^2+k+1$, hence $k^2+k\le n-1<n$ and in particular $k^2+k\le n$. $\square$

FAST REALITY CHECK (exact for small $n$). Define \[ h(n):=\max\{k\ge 1: n+k\ \text{composite and }\ p(n+k)>k\} \] (with $h(n)=\text{None}$ if no such $k$ exists). By Lemma 463.3 it suffices to test $1\le k\le \lfloor(\sqrt{4n+1}-1)/2\rfloor$.

A brute-force script checked $h(n)$ for $2\le n\le 50$ and produced the following (format: $n$, $h(n)$, witness $(m,p(m))$, and the tested bound $k_{\max}$):

 n h(n) witness(m,p) kmax
 2 None         None    1
 3    1       (4, 2)    1
 4 None         None    1
 5    1       (6, 2)    1
 6 None         None    2
 7    2       (9, 3)    2
 8    1       (9, 3)    2
 9    1      (10, 2)    2
10 None         None    2
11    1      (12, 2)    2
12 None         None    3
13    2      (15, 3)    3
14    1      (15, 3)    3
15    1      (16, 2)    3
16 None         None    3
17    1      (18, 2)    3
18 None         None    3
19    2      (21, 3)    3
20    1      (21, 3)    4
21    4      (25, 5)    4
22    3      (25, 5)    4
23    2      (25, 5)    4
24    1      (25, 5)    4
25    2      (27, 3)    4
26    1      (27, 3)    4
27    1      (28, 2)    4
28 None         None    4
29    1      (30, 2)    4
30 None         None    5
31    4      (35, 5)    5
32    3      (35, 5)    5
33    2      (35, 5)    5
34    1      (35, 5)    5
35    1      (36, 2)    5
36 None         None    5
37    2      (39, 3)    5
38    1      (39, 3)    5
39    1      (40, 2)    5
40 None         None    5
41    1      (42, 2)    5
42 None         None    6
43    6      (49, 7)    6
44    5      (49, 7)    6
45    4      (49, 7)    6
46    3      (49, 7)    6
47    2      (49, 7)    6
48    1      (49, 7)    6
49    2      (51, 3)    6
50    1      (51, 3)    6

In particular, one sees the prime-square phenomenon: for $n\in\{43,44,45,46,47,48\}$ the witness is $m=49=7^2$ and the gap $k=49-n$ ranges from $6$ down to $1$.

For $n\le 500$, the ten largest values found were:

(bestk, n, (m,p(m)))
(18, 419, (437, 19))
(18, 343, (361, 19))
(17, 420, (437, 19))
(17, 344, (361, 19))
(16, 477, (493, 17))
(16, 421, (437, 19))
(16, 375, (391, 17))
(16, 345, (361, 19))
(16, 307, (323, 17))
(16, 273, (289, 17))

All of these correspond to witnesses $m=p^2$ with $p\in\{17,19\}$.

5) VERIFICATION.

• Lemma 463.3 uses only the inequality $m\ge p(m)^2$ (true for composite $m$) and the integer step $p(m)\ge k+1$ when $k<p(m)$.
• The brute-force check is exact for each tested $n$ because Lemma 463.3 reduces the search to finitely many $k$.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result. Unconditionally, any admissible gap $k=m-n$ must satisfy $k^2+k\le n$ (Lemma 463.3), so $k=O(\sqrt{n})$. Conversely, for infinitely many $n$ (namely $p^2-p<n<p^2$ with $p$ prime) the choice $m=p^2$ gives a solution with $k$ as large as $p-1\asymp\sqrt{n}$ (Lemma 463.2). Computations up to $n\le 500$ match this prime-square behavior.

(ii) First gap (crisp). Prove (or disprove) that $h(n):=\max\{k: n+k\text{ composite and }p(n+k)>k\}$ satisfies $h(n)\to\infty$ as $n\to\infty$. Equivalently: produce an explicit $f(n)\to\infty$ such that for every sufficiently large $n$ there exists a composite $m=n+k$ with $k>f(n)$ and $p(m)>k$.

(iii) Top 3 next moves.

1. Develop a sieve-theoretic lower bound for the existence of a $k$-rough composite in the short interval $(n+g(n),\,n+\lfloor(\sqrt{4n+1}-1)/2\rfloor]$ for some $g(n)\to\infty$.
2. Try a structured construction beyond prime squares: e.g. semiprimes $m=pq$ with $p\approx q\approx \sqrt{n}$, aiming to force $p(m)=p>m-n$.
3. Computation: for each $n$ search all $k$ up to the exact bound in Lemma 463.3 and study the distribution of $h(n)$ (especially the frequency of $h(n)=\text{None}$) to guess the true order of $\min_{n\le x} h(n)$.

(iv) Minimal counterexample structure. A counterexample to the existence of such an $f$ would require infinitely many large $n$ for which every $k$ in a long initial range (say $1\le k\le K(n)$ with $K(n)\to\infty$) fails: for each such $k$, either $n+k$ is prime or else $p(n+k)\le k$. Any "minimal" obstruction would thus be an $n$ for which all composites in $[n+1,\,n+K(n)]$ have unusually small least prime factor relative to their distance from $n$.