Skip to content

Erdős Problem #385

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

For an integer \(m>1\), let \(p(m)\) be its least prime divisor. Problem 385 studies the largest value of \(m+p(m)\) obtained from a composite integer below \(n\):

\[ F(n)=\max\{m+p(m):1<m<n,\ m\text{ composite}\}. \]

The first question asks whether \(F(n)>n\) for every sufficiently large \(n\). In words, once \(n\) is large enough, must there always be a composite \(m<n\) whose least prime factor reaches far enough to make \(m+p(m)\) pass \(n\)? The second asks whether the excess \(F(n)-n\) eventually becomes arbitrarily large. The maintained page also records a stronger-looking scale question: might the excess be nearly as large as \(\sqrt n\)?

Erdős’s original 1979 wording has the opposite logical polarity: is \(F(n)\le n\) true for infinitely many \(n\)? This is equivalent to asking whether the first maintained-page question has a negative answer. The quantifiers matter: a long finite computation cannot establish either an eventual statement or its negation.

A small example

Take \(n=10\). The composite integers below \(10\) are \(4,6,8,9\). Their least prime divisors and resulting sums are

\[ (m,p(m),m+p(m))=(4,2,6),(6,2,8),(8,2,10),(9,3,12). \]

Therefore \(F(10)=12\), so \(F(10)>10\). This can be reproduced with exact integer arithmetic:

from math import isqrt

n = 10
rows = []
for m in range(1, n):
    divisors = [d for d in range(2, isqrt(m) + 1) if m % d == 0]
    if divisors:
        p = min(divisors)
        rows.append((m, p, m + p))
assert rows == [(4, 2, 6), (6, 2, 8), (8, 2, 10), (9, 3, 12)]
assert max(value for _, _, value in rows) == 12

The calculation verifies one finite instance and checks the definition directly. It says nothing about how often the inequality holds later, and it cannot certify a threshold that works for all sufficiently large \(n\).

What is known

The primary source is Paul Erdős, “Some unconventional problems in number theory,” Acta Mathematica Academiae Scientiarum Hungaricae 33 (1979), 71–80, printed p. 73. There Erdős defines the same \(F(n)\) using composite \(m\) with \(1<m<n\), asks whether \(F(n)\le n\) has infinitely many solutions, and says that plausible conjectures on primes would imply only finitely many. The source presents this as a problem, not as a theorem resolving it.

The maintained Problem 385 page records two comments dated 3 September and 23 September 2026. They report segmented-sieve computations finding no further exceptions in ranges reaching \(10^{11}\) and approximately \(1.0011\times10^{12}\), together with reported lower bounds for the excess on subranges. The page itself warns that comments are user responsibility and are not verified for correctness. They are useful leads, not established external proofs or GCL-certified computation.

Terence Tao’s 2024 discussion explains why the unresolved part is connected to covering intervals by residue classes and to the difficulty of controlling semiprimes at intermediate scales. That exposition is evidence about the analytic shape of the obstacle, not a proof of either question. The live page reports zero proof expositions and zero proof claims.

GCL's current state

The original GCL issue #1655 pins the catalogue at teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. That snapshot records status open, informal status open, solution status unformalized, and statement-formalized metadata yes. The current catalogue commit used for drift checking is 503d0a58ff3b6a12d7ff1665aa37fb953416d85f, blob 97ae243a7fc056bb9c6413ce665b575eadd27ff3; it retains the same Problem 385 status fields.

The issue also pins google-deepmind/formal-conjectures@85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/385.lean, blob f82dc1bdad0cee0c069ff06f67dee03e8103a778. Its definition uses natural numbers and m.minFac, with the composite and \(m<n\) hypotheses encoded in the supremum. It proves a trivial upper bound, but the two main questions and the recorded lower-bound variant end in sorry; the file is an interface, not a proof. The later modularized live file has the same substantive sorry boundary. The V2 ledger alone decides accepted coverage; neither the catalogue flag, the formal file’s presence, nor this article changes that status.

What remains

The smallest clean successor is a bounded, source-reproducible finite audit rather than an attempted solution. Fix a numerical bound \(B\), implement the recurrence

\[ F(n)=\max\bigl(F(n-1),(n-1)+p(n-1)\bigr), \]

including the second term only when \(n-1\) is composite, using an exact segmented least-prime-factor sieve. Publish the bound, source revision, output hash, and the complete exception list for \(F(n)\le n\). Acceptance is byte-for-byte agreement with an independently rerun implementation and direct checks at every reported exception; a mismatch falsifies the certificate and stops the task. The stopping rule is the fixed bound and two agreeing runs, not an extrapolation to infinity.

The global missing ingredient is not finite enumeration. It is a theorem controlling the relevant composite or semiprime survivors uniformly over the intermediate interval scales that can defeat \(m+p(m)>n\). No such theorem was established in this audit.

Sources and claim boundaries

This article separates the original problem, finite verified arithmetic, unverified external reports, and formal source metadata. It does not certify a proof, promote a computational claim, or decide accepted coverage.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1655 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction