Is $\max_{m<n}(m+p(m))>n$ eventually and does the excess diverge? (Erdős #385)
Statement
For a composite integer $m$ let $p(m)$ denote its least prime factor, and define $$F(n) = \max_{\substack{m<n\\ m\text{ composite}}} \big(m + p(m)\big).$$ Since a composite $m$ has $p(m)\leq \sqrt{m}<\sqrt{n}$, trivially $F(n)\leq n+\sqrt{n}$. Two questions: is $F(n)>n$ for all sufficiently large $n$? And does $F(n)-n\to\infty$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean — a statement formalisation already exists — preferred, else a full written proof) that $F(n)>n$ for all sufficiently large $n$, together with a proof that $F(n)-n\to\infty$ (or a disproof of either). ADVANCES (each independently checkable): a proof of a nontrivial unconditional lower bound of the form $F(n)\geq n+g(n)$ for an explicit unbounded $g$, improving on what is stated in the background; OR a proof of $F(n)>n$ for all large $n$ conditional on a clearly stated hypothesis (prime-gap or parity-type), with the conditional proof; OR a reproducible exact computation of $F(n)$ for all $n\leq N$ at a new record $N$, extending OEIS A322292, listing every $n\leq N$ with $F(n)\leq n$ and reporting the empirical behaviour of $F(n)-n$, with source code and certificates. Deliver the proof file, the conditional proof, or the computation code plus the extended table and the complete list of exceptional $n$.
Background
A question of Erdős, Eggleton, and Selfridge, recorded in [Er79d, p.73] and [ErGr80, p.74]; listed as open on erdosproblems.com/385 (fetched 2026-07-13, status 'open', tagged 'number theory'). They note that 'plausible conjectures on primes' imply $F(n)\leq n$ for only finitely many $n$ (so $F(n)>n$ eventually), and speculate that in fact $F(n)\geq n+(1-o(1))\sqrt{n}$ always — close to the trivial ceiling $F(n)\leq n+\sqrt{n}$. Intuitively $F(n)>n$ asks for a composite $m$ just below $n$ whose least prime factor exceeds $n-m$; the extremal $m$ are those with an unusually large least prime factor (near $\sqrt{m}$), i.e. products of two nearby primes. Terence Tao has analysed the problem (blog post, 19 Aug 2024), connecting it to the parity problem and to the exclusion of Siegel zeroes. Sarosh Adenwalla (site comments) observed that the first question is equivalent to Erdős #430 (erdosproblems.com/430). The relevant values are tabulated as OEIS A322292, and a Lean formalisation exists in the DeepMind formal-conjectures repository. The problem sits alongside the venue problems on $m+\omega(m)\leq n$ (Erdős #413) and $m+\tau(m)$ (Erdős #647). The attacker's tool: sieve computation of $p(m)$ for all $m<n$ to evaluate $F(n)$ exactly over a large range, locate every $n$ with $F(n)\leq n$, and empirically track $F(n)-n$ against the conjectured $(1-o(1))\sqrt{n}$; the theorem itself requires parity-breaking analytic input.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #385 (T. F. Bloom) | website |
| REF-02 | OEIS A322292 — sequence associated with Erdős #385 (max of m + least-prime-factor(m) over composite m<n) | website |
| REF-03 | Terence Tao — Erdős problem 385, the parity problem and Siegel zeroes (blog) | website |
| REF-04 | Lean formalisation of Erdős #385 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.