Erdős Problem #385

Erdős Problem #385

1) ROUND-2 OBJECTIVE

I pursue (C) obstruction/partial reduction. Round-1 already localized every possible bad value of $n$ to the even prime-shift case $n=p+1$, so the most promising next step is not to re-run the original argument but to extract sharp consequences from the Round-1 bounds. The goal in this round is to prove two genuinely stronger statements: first, that the set of bad integers has density $0$; second, that the trivial upper bound $F(n)-n\leq \sqrt n$ is attained on the correct scale infinitely often, in the precise sense that \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}=1. \]

2) Round-1 FOUNDATION USED

I use the following Round-1 results.

1. Round-1 Lemma 1: if $n\geq 5$ is odd, then $F(n)\geq n+1$.
2. Round-1 Lemma 2: if $n\geq 6$ is even, then $F(n)\geq n$.
3. Round-1 Lemma 3: if $n\geq 6$ is even and $n-1$ is composite, then $F(n)>n$.
4. Round-1 Corollary 4: if $F(n)\leq n$, then $n$ is even, $n-1$ is prime, and in fact $F(n)=n$.
5. Round-1 Lemma 5: for $n=q^2+1$ with $q$ prime, one has $F(n)-n\geq q-1$.
6. Round-1 Lemma 6: for all $n\geq 5$, one has $F(n)\leq n+\sqrt n$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new idea is to combine the Round-1 square-sequence lower bound with the Round-1 trivial upper bound at the level of the normalized ratio $(F(n)-n)/\sqrt n$. This turns the earlier weak statement \[ \limsup_{n\to\infty}(F(n)-n)=\infty \] into the sharp asymptotic statement \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}=1. \] A second new observation is that Round-1 Corollary 4 immediately forces the bad set into a subset of the shifted primes $\{p+1\}$, giving an unconditional zero-density theorem.

4) ATTACK PLAN (ROUND-2)

The exact gaps left after Round-1 were:

1. The main questions $F(n)>n$ eventually and $F(n)-n\to\infty$ were still open.
2. The earlier lower bound only showed that $F(n)-n$ is unbounded on a subsequence, without identifying the true maximal order.
3. The earlier reduction to the case $n-1$ prime had not yet been converted into a density statement.

The plan is therefore:

1. Use Round-1 Lemmas 5 and 6 together to pin down the exact value of the limsup ratio.
2. Use Round-1 Corollary 4 together with the prime number theorem to show that bad integers have density $0$.

This does not solve the original problem, but it does close two concrete gaps left by Round-1.

5) WORK (ROUND-2)

Theorem 385.1. One has \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}=1. \]

Proof. Round-1 Lemma 6 gives the uniform upper bound \[ \frac{F(n)-n}{\sqrt n}\leq 1 \qquad (n\geq 5), \] so \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}\leq 1. \] On the other hand, if $q$ is prime and $n=q^2+1$, then Round-1 Lemma 5 gives \[ F(n)-n\geq q-1. \] Hence along this subsequence \[ \frac{F(n)-n}{\sqrt n} \geq \frac{q-1}{\sqrt{q^2+1}}. \] As $q\to\infty$, the right-hand side tends to $1$. Therefore \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}\geq 1. \] Combining the upper and lower bounds gives the claim. $\square$

Corollary 385.2. The bad set \[ \mathcal B:=\{n\geq 5: F(n)\leq n\} \] has natural density $0$. More precisely, \[ \#\{n\leq x: F(n)\leq n\}\leq \pi(x-1)+O(1)=o(x). \] In particular, almost all integers are good.

Proof. By Round-1 Corollary 4, every bad integer $n\geq 6$ is even and satisfies $n-1$ prime. Thus \[ \{n\leq x: F(n)\leq n\}\subseteq \{p+1\leq x: p\text{ prime}\}\cup\{5\}. \] Hence \[ \#\{n\leq x: F(n)\leq n\}\leq \pi(x-1)+1. \] Since $\pi(x)=o(x)$, the density is $0$. $\square$

Corollary 385.3. The trivial upper bound from Round-1 is asymptotically best possible on an infinite subsequence: for infinitely many $n$, \[ F(n)=n+(1-o(1))\sqrt n. \]

Proof. This is just a restatement of Theorem 385.1. $\square$

6) ADVERSARIAL VERIFICATION

The new work has three places where hidden issues could occur.

1. Could the subsequence $n=q^2+1$ fail to be admissible? No. For every prime $q$, the integer $m=q^2<n=q^2+1$ is composite, so Round-1 Lemma 5 applies exactly.
2. Could the upper bound be too weak to identify the limsup ratio? No. The bound $F(n)-n\leq \sqrt n$ is uniform in $n$, while the square subsequence gives ratios tending to $1$ from below, so the limsup is forced to be exactly $1$.
3. Could the density-zero claim miss some bad odd numbers? No. Round-1 Lemma 1 already ruled out all odd $n\geq 5$, and Round-1 Corollary 4 completely characterizes the only possible bad numbers.

No quantifier problem remains in the new claims.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance beyond Round-1 is twofold:

1. a sharp normalized limsup theorem, \[ \limsup_{n\to\infty}\frac{F(n)-n}{\sqrt n}=1, \] which substantially strengthens the earlier statement that $F(n)-n$ is merely unbounded on a subsequence;
2. an unconditional density theorem: the bad set has density $0$, so almost all integers are good.

The original eventual-positivity question and the full limit $F(n)-n\to\infty$ remain open.

8) COMPLETION ESTIMATE

COMPLETION: 48%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #385, erdosproblems.com/385, accessed 2026-03-07.
2. T. Tao, Erdos problem #385, the parity problem, and Siegel zeroes, blog post, 2024.

OBJECTIVE AND SOURCE REVIEW

Erdős #385; independent attempt, 2026-09-23. For $F(n)=\max_{m<n,\ m\text{ composite}}(m+p(m))$, where $p(m)$ is the least prime factor, is $F(n)>n$ eventually, and does $F(n)-n\to\infty$? I read all of 385.tex. Its density-zero exceptional-set result and square-subsequence limsup do not control the universal lower limit. I derive an exact local test and independently check a finite range.

WORK: FINITE LOCAL WINDOW

For composite $m<n$, $p(m)\le\sqrt m<\sqrt n$. Therefore $m+p(m)>n$ can hold only when \[ n-\sqrt n<m<n. \] More generally $F(n)-n>h$ is equivalent to existence of an integer $j\ge1$ with $j<\sqrt n-h$, $n-j$ composite, and $p(n-j)>j+h$. This is simply the original inequality with $m=n-j$, but localizes every possible witness and separates compositeness from absence of small factors. Prime candidates do not qualify. The exact running maximum obeys \[ F(n+1)=\max\left(F(n),\ n+p(n)\right) \] when $n$ is composite, and $F(n+1)=F(n)$ otherwise. A least-prime-factor sieve and this recurrence, saved in verification/batch_3_digits_records.py, found exactly 100 integers $5\le n\le10^6$ with $F(n)\le n$. The last three are $8742,267672,267680$; the complete list is saved in JSON. This is a bounded check, not a claim that these are all exceptions.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The recurrence adds $m=n$ only when moving from $F(n)$ to $F(n+1)$, respecting the strict inequality $m<n$. The sieve treats primes separately and initializes with the composite $4$ when computing $F(5)$. A very long interval with no new exceptions does not imply eventual positivity. To prove the original assertions one needs composite numbers in every relevant local window whose least prime factor beats their distance to $n$, uniformly for arbitrarily large $n$; neither a density statement nor square examples achieve this.

SOURCES CHECKED

Complete local source gpt_pro_5.4/385.tex; exact definition and both questions checked at the indexed primary page https://www.erdosproblems.com/385, 2026-09-23.

FINAL

UNRESOLVED. An exact local criterion and a reproducible finite check are supplied; universal eventual behavior is unproved.

COMPLETION ESTIMATE

Conservative subjective progress toward the eventual statements. COMPLETION: 10%

Problem #385

FORMAL RESTATEMENT

For an integer $m\ge 2$, let $p(m)$ denote the least prime divisor of $m$. Define, for integers $n\ge 5$, \[ F(n)\ :=\ \max_{\substack{m<n\\ m\ \text{composite}}}\ \left(m+p(m)\right). \] The problem asks:

1. Is there an $N$ such that for all $n\ge N$ one has $F(n)>n$?
2. Does $F(n)-n\to\infty$ as $n\to\infty$ (i.e. for every $M$ there is $N_M$ such that $n\ge N_M\Rightarrow F(n)-n\ge M$)?

QUICK LITERATURE/CONTEXT CHECK

This is Erdős problem #385 in the Erdős Problems database. It is presented as open there, with the remark that "plausible conjectures on primes" suggest $F(n)\le n$ only finitely often and that perhaps $F(n)\ge n+(1-o(1))\sqrt{n}$ might hold; also note the trivial upper bound $F(n)\le n+\sqrt{n}$. Terence Tao has a detailed blog discussion relating the difficulty of ruling out $F(n)\le n$ to the parity barrier in sieve theory and to controlling gaps between certain almost primes (e.g. semiprimes with restricted factor ranges). The database notes an equivalence to another formulation (problem #[430] there) and a related question (problem #[463] there).

ATTACK PLAN

Write the inequality $m+p(m)>n$ as $p(m) > n-m$. Thus to prove $F(n)>n$ it suffices to find, for each large $n$, a composite $m$ in some short interval $[n-h,n)$ with least prime factor exceeding $h$ (i.e. an $h$-rough composite). Potential approaches suggested by the literature:

• Reduce to locating semiprimes (or more generally $y$-rough integers) in intervals of length comparable to $y$.
• Use sieve-theoretic estimates for rough numbers in short intervals; the main obstruction is that existing methods struggle to guarantee at least one survivor uniformly in $n$ at the relevant intermediate scales.
• Try to build explicit families of "bad" $n$ with $F(n)=n$ (disproof of (a)), or conversely show that such families cannot persist beyond some scale (proof of (a)).

WORK

We record several unconditional observations.

Lemma 1 (odd $n$ are trivially good). If $n\ge 5$ is odd, then $F(n)\ge n+1$ (hence $F(n)>n$).

Lemma 2 (even $n$ satisfy $F(n)\ge n$). If $n\ge 6$ is even, then $F(n)\ge n$.

Lemma 3 (even $n$ with $n-1$ composite are good). If $n\ge 6$ is even and $n-1$ is composite, then $F(n)>n$.

Corollary 4 (structure of possible counterexamples to (a)). If $n\ge 6$ and $F(n)\le n$, then $n$ must be even, $n-1$ must be prime, and necessarily $F(n)=n$.

Lemma 5 (easy limsup lower bound). Along the subsequence $n=q^2+1$ with $q$ prime one has $F(n)-n\ge q-1\to\infty$. In particular, \[ \limsup_{n\to\infty}\left(F(n)-n\right)=\infty. \]

Lemma 6 (trivial upper bound). For all $n\ge 5$, $F(n)\le n+\sqrt{n}$.

Computational sanity check (not a proof). A brute-force computation for $n\le 200$ shows that $F(n)=n$ for \[ n\in\{6,8,12,14,18,20,24,30,32,42,44,48,60,62,72,74,84,90,102,104,108,110,114,132,140,168,182,198,200\}, \] and $F(n)>n$ for all other $5\le n\le 200$.

VERIFICATION

The above lemmas are elementary and were checked symbolically:

• Lemmas 1--3 are direct constructions of a single admissible composite $m<n$.
• Corollary 4 is a direct logical combination of Lemmas 1--3.
• Lemma 5 uses the explicit choice $m=q^2$; no hidden assumptions.
• Lemma 6 uses the classical bound $p(m)\le \sqrt{m}$ for composite $m$.

None of these steps address the main difficulty: ruling out infinitely many even $n=p+1$ with $p$ prime and $F(n)=n$.

FINAL

UNRESOLVED.

Most promising partial results obtained above:

• Complete reduction: any counterexample to eventual positivity must be even and of the form $n=p+1$ with $p$ prime (Corollary 4).
• $\limsup (F(n)-n)=\infty$ (Lemma 5), and always $F(n)\le n+\sqrt{n}$ (Lemma 6).

Specific barrier:

• One must control existence of $h$-rough composite numbers in intervals $[n-h,n)$ at intermediate scales (roughly $\log n \ll h \ll \sqrt{n}$), which is tightly connected to the parity problem in sieve theory.

Smallest missing step to a full resolution:

• Prove (or disprove) that for all sufficiently large primes $p$ there exists a composite $m<p+1$ with $m+p(m)>p+1$; equivalently, show that for each large prime $p$ one can find an $h$ and a composite $m\in[p+1-h,p]$ whose least prime factor exceeds $h$.

COMPLETION ESTIMATE

COMPLETION: 35%