Erdoes #385 - working report - Erdős Problem a Day

Erdős problem #385 — wave 9a

Accessed 2026-07-28. Claim labels used below are:

(a) elementary-rigorous;
(b) rigorous modulo the named theorem;
(c) plausible/structural-unverified;
(d) computational-only.

0. Mandatory live-page check

I fetched the live page and its LaTeX view through the Bright Data browser, rather than datacenter curl.

The page said:

status OPEN;
0 comments on this problem;
0 claimed proofs for this problem;
“Interested in collaborating”: None;
“Currently working on this problem”: None;
“This problem looks difficult”: TerenceTao;
“This problem looks tractable”: None.

Thus none of the mandatory stop conditions applied.

The verbatim statement from the live LaTeX view is:

Let\[F(n) = \max_{\substack{m<n\\ m\textrm{ composite}}} m+p(m),\]where $p(m)$ is the least prime divisor of $m$. Is it true that $F(n)>n$ for all sufficiently large $n$? Does $F(n)-n\to \infty$ as $n\to\infty$?

The live page cites [Er79d,p.73] and [ErGr80,p.74], and records the following known context.

Erdős, Eggleton, and Selfridge said that plausible prime conjectures imply

that $F(n)\le n$ only finitely often, and suggested the possible lower bound $F(n)\ge n+(1-o(1))\sqrt n$. The elementary upper bound is $F(n)\le n+\sqrt n$.

It links Tao's 2024 discussion.
It says that the first question is equivalent to

problem #430, and also points to problem #463.

It marks the statement as formalised and links OEIS

A322292.

There is an apparent sign typo in the live explanatory paragraph: it says $a_j-p(a_j)>n$, although #430 has $a_j<n$. The stated conclusion follows from $p(a_j)>n-a_j$, namely $a_j+p(a_j)>n$. I use this mathematically forced plus sign below and do not silently treat the displayed minus sign as a theorem.

1. Source and literature audit

The original primary source was checked directly. Page 73 of Erdős, “Some unconventional problems in number theory,” Acta Math. Acad. Sci. Hungar. 33 (1979), 71–80, defines the same $F$, asks whether $F(n)\le n$ infinitely often, and says that plausible prime conjectures give only finitely many such $n$. This is equivalent to the live page's first question.

The live bibliography identifies [ErGr80] as P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique (1980). I did not find an accessible primary scan of the cited passage. There is also a pagination discrepancy: the live page says p.74, while Tao's post says p.92. I therefore make no source-specific claim about that passage beyond what the authoritative live page records.

Tao's post is the only directly relevant later research discussion found. It proves the useful conditional reduction that, for any fixed $2<u<3$, an $o(x^{1/u})$ upper bound for gaps between semiprimes in $[x,2x]$ whose prime factors lie in $[x^{1/u},x^{1-1/u}]$ would settle both questions affirmatively. It also explains that presently available prime/semiprime gap technology does not reach this scale even under RH, and identifies the parity barrier and possible Siegel zeros as obstructions.

I searched exact phrases and formulae from the problem, “Erdős problem 385,” and the semiprime-gap formulation on the general web and arXiv, and followed the links/citations above. I found no paper claiming a later solution or a stronger theorem specific to #385. This is an honest search miss, not a claim that no such literature can exist.

For a data sanity check only, the independently computed values agree with all 9,996 entries $5\le n\le10000$ in the OEIS table. The OEIS data were not used as input.

2. Exact elementary reductions

Write $P^-(m)$ for the least prime factor of $m$.

2.1 Only a prime plus one can be bad

For every $n\ge5$, $F(n)\ge n$. More precisely: (a)

If $n$ is odd, $m=n-1$ is even composite and

$m+P^-(m)=n+1$.

If $n$ is even and $n-1$ is composite, it is odd, so

$m=n-1$ gives $m+P^-(m)\ge n+2$.

In the remaining case $n=r+1$, where $r$ is an odd prime,

$m=n-2$ is even composite and $m+P^-(m)=n$.

Consequently,

F(n)\le n\quad\Longleftrightarrow\quad F(n)=n,

and equality is possible only when $n=r+1$ for an odd prime $r$. In particular the number of bad $n\le x$ is at most $\pi(x)$, hence is $O(x/\log x)$ by Chebyshev's bound. (b: Chebyshev)

2.2 A one-variable rough-number criterion

Let $n=r+1$, with $r$ an odd prime. Even $m<n$ cannot make $m+P^-(m)>n$. Every relevant odd $m$ is $m=r-2k$, and $n-m=2k+1$. Therefore (a)

F(r+1)>r+1 \quad\Longleftrightarrow\quad \exists k\ge1:\quad \begin{cases} r-2k\text{ is composite},\\ P^-(r-2k)>2k+1. \end{cases} \tag{1}

The search is automatically finite: a composite $m$ has $(P^-(m))^2\le m$, so a successful $k$ must satisfy

(2k+1)^2<r-2k,\qquad\text{or equivalently}\qquad 4k^2+6k+1<r. \tag{2}

Thus the exact missing uniform lemma for the first question is:

For every sufficiently large odd prime $r$, there is a $k$ satisfying (1), necessarily in the range (2).

This is equivalent to the first question, not merely sufficient.

2.3 Exact semiprime quotient reduction, including a margin

Fix $H\ge0$ and put $x=n+H$. Suppose $a,q$ are primes with $a\le q$, and write

q=\left\lfloor\frac{x}{a}\right\rfloor,\qquad s=x-aq.

Then the semiprime $m=aq$ satisfies

m<n\quad\hbox{and}\quad m+a>n+H

if and only if

H<s<a. \tag{3}

Indeed, $m<n=x-H$ is $s>H$, while $m+a>x$ is $s<a$. Since $P^-(m)=a$, (3) gives $F(n)-n>H$. Conversely, every semiprime witness has this form. (a)

For $H=0$, this becomes the particularly simple sufficient criterion used in the independent computation:

\exists\text{ prime }a<\sqrt n,\quad a\nmid n,\quad \left\lfloor\frac n a\right\rfloor\text{ prime}. \tag{4}

This is the semiprime formulation noted by Will Sawin in the comments on Tao's post. Formula (3) also isolates a concrete sufficient lemma for the second question: for every fixed $H$, establish (3) for every sufficiently large $n$. Current methods do not provide that worst-case uniformity.

3. Exact computation through $10^9$

3.1 Result

The following finite statements are (d).

Exactly 100 integers $5\le n\le10^9$ satisfy $F(n)\le n$. In every

case $F(n)=n$, as the elementary reduction requires.

The last two are $267672$ and $267680$. Hence

\[ F(n)>n\qquad(267680<n\le10^9). \]

At the endpoint,

\[ F(10^9)=1\,000\,029\,122. \] A maximizing witness is \[ m=999\,999\,361=29\,761\cdot33\,601, \] so $P^-(m)=29\,761$ and $m+P^-(m)=1\,000\,029\,122$.

The complete equality list is

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, 234, 240,
242, 270, 272, 282, 284, 312, 314, 318, 354, 360, 390, 420, 422, 434,
462, 464, 468, 510, 572, 648, 660, 662, 762, 840, 884, 888, 942, 1064,
1110, 1302, 1304, 1308, 1430, 1434, 1440, 1452, 1454, 1488, 1490,
1494, 1500, 1572, 2004, 2114, 2352, 2394, 2400, 2622, 2688, 2690,
2694, 2700, 2862, 2970, 2972, 3042, 3540, 3542, 4290, 4974, 5418,
5420, 5852, 5862, 5880, 5882, 8742, 267672, 267680

Its SHA-256, using the ASCII comma-separated list with no spaces, is 4b39cc3f910b196dcc454eb6fd11018d037012ee90b7956b6478efe3c6e1f5b4.

3.2 Sharp finite tail bounds

For each $K$, the middle column is the last $n\le10^9$ for which $F(n)-n<K$. Therefore the bound $F(n)-n\ge K$ holds for every larger $n$ through $10^9$, and the left endpoint cannot be lowered. (d)

| $K$ | last $n$ with $F(n)-n<K$ | $F(n)-n$ there | |---:|---:|---:| | 1 | 267,680 | 0 | | 2 | 267,683 | 1 | | 4 | 267,683 | 1 | | 8 | 267,689 | 7 | | 16 | 267,689 | 7 | | 32 | 267,779 | 31 | | 64 | 267,779 | 31 | | 128 | 410,429 | 119 | | 256 | 1,064,423 | 255 | | 512 | 1,895,149 | 501 | | 1,024 | 5,851,049 | 1,021 | | 2,048 | 16,348,153 | 1,939 | | 4,096 | 46,981,117 | 3,555 | | 8,192 | 162,826,889 | 7,849 | | 16,384 | 521,111,629 | 16,345 |

For example, the strongest last row says

F(n)-n\ge16384\qquad (521\,111\,629<n\le10^9). \tag{5}

These values are not a monotonicity claim about $F(n)-n$; they are exact minima over the indicated finite tails.

For another view, the exact minimum of $F(n)-n$ on each large decimal slab is:

| interval | minimum | first attaining $n$ | |---|---:|---:| | $10^4\le n<10^5$ | 1 | 10,349 | | $10^5\le n<10^6$ | 0 | 267,672 | | $10^6\le n<10^7$ | 255 | 1,064,423 | | $10^7\le n<10^8$ | 1,417 | 10,702,487 | | $10^8\le n\le10^9$ | 6,041 | 109,505,933 |

3.3 Independent semiprime certificate

There are 50,847,532 potentially bad values $n=r+1\le10^9$, with $r\ge5$ prime. The independent search using (4) found semiprime witnesses for 50,847,412 of them. The remaining 120 all satisfy $n\le267680$. (d)

The maximum, over all covered candidates, of the least witnessing prime $a$ was only $1439$. It occurred at

n=928\,991\,252,\quad q=\left\lfloor n/1439\right\rfloor=645\,581,\quad n\bmod1439=193.

Both $1439$ and $645581$ are prime, so

m=1439\cdot645581=928\,991\,059<n<m+1439.

The 100 exact equality cases are a subset of the 120 semiprime-uncovered cases. The other 20 are

278, 578, 608, 938, 1188, 1328, 1628, 2012, 2018, 2112, 2348, 2742,
4028, 4970, 5868, 5870, 6152, 17352, 33638, 33642

and are covered by composites having at least three prime factors, counted with multiplicity. This explains exactly why the two independent lists are close but not identical.

4. Algorithms, correctness, and reproducibility

The standalone checker is erdos385_wave9a_reverify.py. It contains both independent algorithms and frozen assertions for every number reported above. It requires Python 3 and NumPy.

python3 runs/erdos385_wave9a_reverify.py

The full rerun printed all frozen report values reproduced exactly and took 120.35 seconds with 2,062,972 KiB peak RSS. Its source SHA-256 is a8dfb022335c18f27c1ec5565beabbae976c9f57fa82be28ee92c439dbd4876d.

The exact scan works as follows.

Sieve the base primes through $\sqrt{10^9}$.
In consecutive blocks of $m$, mark each composite by its least prime

factor. Primes are left marked zero.

Form $E(m)=m+P^-(m)$ for composites and take a prefix maximum. On

incorporating $m=n-1$, that prefix maximum is exactly $F(n)$.

Carry the previous block's maximum into the next block.

The recurrence is just

F(n)=\max\left(F(n-1), (n-1)+P^-(n-1)\,\mathbf 1_{n-1\ {\rm composite}}\right),

with the second entry omitted for a prime. Thus no probable-prime test, floating-point comparison, or heuristic is involved. (a: algorithm correctness; d: its $10^9$ output)

Before the large run, a literal implementation of the defining maximum was compared with the recurrence for all $5\le n\le500$, with no mismatch.

The second implementation, erdos385_semiprime_scan.cpp, uses no least factor or prefix-maximum array. It builds an odd prime sieve and tests (4) for each candidate. Its source SHA-256 is 4aef61af186fd7774cebcddff7e71b71e42a7cb17850a6ab754c04dcf8a219db.

g++ -O3 -march=native -std=c++20 -Wall -Wextra -pedantic \
  runs/erdos385_semiprime_scan.cpp -o /tmp/erdos385_semiprime_scan
/tmp/erdos385_semiprime_scan 1000000000

This independently returned 50,847,532 candidates, 50,847,412 witnessed candidates, 120 uncovered candidates, last uncovered $267680$, and largest least witness $a=1439$. It took 20.63 seconds and 491,616 KiB peak RSS. The NumPy checker independently regenerates the same 120-member set by a batched quotient-primality algorithm; its set hash is 97baee506b870570a7e7c9b43c0c5b9b5433e498822eac27cda7b696970a6ff1.

5. What remains and why standard machinery stalls

The computation is finite and does not prove either asymptotic statement. The exact missing input for the first question is the uniform prime-indexed rough-number lemma (1)–(2). A clean sufficient special case is the uniform semiprime condition (4). For the second question, even the semiprime special case requires (3), uniformly in $n$, for every fixed margin $H$.

Tao's analysis shows why this is not a routine sieve estimate. At the useful intermediate scales, one needs worst-case short intervals containing semiprimes with both factors restricted away from small primes. Standard sieves encounter the parity barrier; known gap bounds do not provide the required interval length, even if RH is assumed. Tao further explains how a Siegel-zero scenario can reinforce rather than remove this obstruction. Accordingly, the missing lemma is a uniform short-interval rough-semiprime theorem, not more optimization of the finite scan. (c as a diagnosis, supported by Tao's cited analysis)

The exact scan costs $O(N\log\log N)$ time and segmented $O(B+\sqrt N)$ storage. At the observed rate, merely extending it to $10^{12}$ would cost about $10^3$ times as much, roughly 22 core-hours (about US$1–$2 at $0.05–$0.10/core-hour, before instance and storage overhead). The dense independent prime audit would require roughly terabyte-scale arrays and would need redesign. No finite endpoint, however large, supplies the missing uniformity.

PARTIAL: Exactly 100 values n<=10^9 have F(n)<=n, all equalities and the last n=267680; also F(n)-n>=16384 for 521111630<=n<=10^9, while the uniform rough-semiprime lemma needed for either asymptotic question remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger