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

Erdős problem #430 — wave 9i

Access date: 2026-07-28 (UTC).

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser path, not datacenter curl: Erdős problem #430.

The exact live wording includes “Fix some integer \(n\) and define a decreasing sequence in \([1,n)\)”, with the definition

a_1=n-1,\qquad a_k=\max\{a\in\mathbb Z:1\leq a<a_{k-1},\ p>n-a\text{ for every prime }p\mid a\}\quad(k\geq2).

The exact question sentence is:

“Is it true that, for sufficiently large \(n\), not all of this sequence can be prime?”

This is an exact symbolic transcription of the live statement; the two quoted fragments reproduce its wording. The example on the page (\(n=8\) gives \(7,5\), then stops) fixes the intended convention that \(1\) is not appended.

Live metadata:

| Field | Live value | |---|---| | Status | OPEN | | Comments | 0 | | Claimed proofs | 0 | | Interested in collaborating | None | | Currently working on this problem | None | | “Looks difficult” | TerenceTao | | Formalised statement | No |

Therefore none of the mandatory stop conditions applies.

The page records two known observations:

Erdős and Graham report Selfridge's preliminary calculations in favor of

the conjecture, with no proof.

Sarosh Adenwalla observed equivalence with the first question in

problem #385.

1. Literature check

I located and checked the following sources themselves.

P. Erdős, [*Some unconventional problems in number

theory](https://combinatorica.hu/~p_erdos/1979-23.pdf), Acta Math. Acad. Sci. Hungar.* 33 (1979), 71–80. On p. 73 it defines \[ F(n)=\max_{\substack{m<n\\m\ {\rm composite}}}(m+p(m)), \] where \(p(m)\) is the least prime divisor, asks whether \(F(n)\leq n\) infinitely often, and says plausible prime conjectures predict only finitely many such \(n\).

P. Erdős and R. L. Graham, [*Old and New Problems and Results in

Combinatorial Number Theory*](https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf), Monographie 28 de L'Enseignement Mathématique (1980). The \(F(n)\) formulation is on p. 74. The increasing-distance version that becomes live problem #430 after replacing \(a\) by \(n-a\) is on p. 35.

T. Tao, [*Erdos problem #385, the parity problem, and Siegel

zeroes*](https://terrytao.wordpress.com/2024/08/19/erdos-problem-385-the-parity-problem-and-siegel-zeroes/) (19 August 2024). This gives the semiprime-gap reduction and explains the parity/Siegel-zero obstruction.

OEIS A322292 is \(F(n)\), and

A322293 lists \(n\) with \(F(n)\leq n\). Its b-file says its 100 listed terms are all terms through \(10^8\).

Targeted searches using both problem numbers, the exact \(F(n)\) formula, “least prime divisor”, and “semiprime gaps” found no paper claiming a solution or further theorem specifically for #385/#430. This is a search miss, not a proof that no such literature exists. Erdős's promised Eggleton–Erdős–Selfridge paper was not found; Tao likewise says that, to his knowledge, it never appeared.

2. Exact reduction

Here and below:

[a] means elementary-rigorous;
[b] means rigorous modulo the named theorem;
[c] means plausible/structural-unverified;
[d] means computational-only.

Let \(\ell(m)\) be the least prime divisor of every integer \(m>1\) (so \(\ell(m)=m\) when \(m\) is prime).

[a] Equivalence. The live greedy sequence simply enumerates, in decreasing order, all \(m\in(1,n)\) satisfying

\ell(m)>n-m.

Consequently it contains a composite term if and only if

\exists\,m<n,\quad m\ {\rm composite},\quad m+\ell(m)>n,

or equivalently \(F(n)>n\).

Call \(n\) bad when \(F(n)\leq n\).

[a] Parity reduction.

If \(n\geq5\) is odd, \(m=n-1\) is even composite and

\(\ell(m)=2>n-m=1\). Thus every odd \(n\geq5\) is good.

If \(n\geq6\) is even, \(m=n-2\) gives \(m+\ell(m)=n\), so \(F(n)\geq n\).
If this even \(n\) also has \(n-1\) composite, then

\((n-1)+\ell(n-1)\geq n+2\), so it is good.

Hence

n\text{ bad}\ \Longrightarrow\ n=p+1\text{ for an odd prime }p, \qquad F(n)=n. \tag{1}

In particular, bad integers already have density zero [b, using the prime number theorem; only the much weaker fact \(\pi(x)=o(x)\) is needed].

[a] Finite test for one candidate \(n\). Put \(h=n-m\). For even \(n\), an admissible \(h\) must be odd: if \(h\) is even then \(m\) is even and \(\ell(m)=2\leq h\). If \(m\) is composite and \(\ell(m)>h\), then

h^2<\ell(m)^2\leq m=n-h,

so \(h^2+h<n\). Therefore, after (1), \(n=p+1\) is bad exactly when there is no odd \(h\) such that

3\leq h,\qquad h^2+h<n,\qquad n-h\text{ composite},\qquad \ell(n-h)>h. \tag{2}

This isolates a finite, exact test for each \(n\), but does not make that test uniform in \(n\).

3. A checkable interval certificate

[a] Semiprime interval lemma. Let \(r\leq s\) be odd primes and set \(m=rs\). Then \(\ell(m)=r\). Every even integer

\[ m<n<m+r \]

is good, witnessed by this same \(m\). Equivalently, the semiprime certifies all even integers

n\in\{m+1,m+3,\ldots,m+r-2\}. \tag{3}

Thus a chain of overlapping intervals (3) is a compact certificate for a whole finite range. I used only balanced semiprimes \(r\leq s\leq2r\) above \(10^7\).

The standalone checker erdos430_wave9i_reverify.py does the following from scratch, using only the Python standard library:

It constructs a least-prime-factor sieve through \(10^7\), evaluates

\(F(n)\) exactly there, and compares the resulting exceptional list with the embedded list.

It separately trial-divides every reported exception and directly checks

(2), so the exceptional values are not trusted merely because they were embedded.

For \(10^7<n\leq10^{10}\), it regenerates all relevant balanced

semiprimes in increasing order by a heap merge and greedily verifies an overlap chain of intervals (3). It does not read a precomputed certificate.

Run:

python runs/erdos430_wave9i_reverify.py

Observed output on this VM:

prefix=10000000
limit=10000000000
bad_count=100
bad_count_through_1000=58
bad_count_through_10000=98
bad_count_through_100000=98
bad_count_through_1000000=100
bad_count_through_10000000=100
bad_count_through_100000000=100
bad_count_through_1000000000=100
bad_count_through_10000000000=100
cover_start=10000002
cover_selected_intervals=207826
cover_examined_intervals=28590773
cover_last_right=10000086406
cover_sha256=1931b281ac319bfebae3d1a835ca0330463e7fb3ece07641a171efd6e3439589
elapsed_seconds=34.856
VERIFIED

The run used about 39 MB resident memory and 34.9 CPU-seconds. The script's SHA-256 after this run is e5fa9f909a87c1576282d612491373dd187bbbbe9480396571c664f53a710d6a.

An auxiliary, independently written C++ interval generator erdos430_wave9i_search.cpp also produced a 69,941-interval cover through \(10^9\); its emitted audit file is erdos430_wave9i_certificate.csv. The main result does not depend on that file.

4. Exact finite result

[d] Verified theorem for the computed regime. For \(5\leq n\leq10^{10}\), the live sequence consists entirely of primes exactly for the following 100 values:

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.

Equivalently, these are exactly the \(n\) in that range with \(F(n)=n\); all other \(n\) in the range satisfy \(F(n)>n\). The last exception is \(267680\).

The OEIS b-file already claimed the same list was complete through \(10^8\). The independently regenerated interval proof above extends the verified range by a factor of 100.

This is a finite statement only. It is not evidence of a proved cutoff and does not close the Erdős problem.

5. Exact remaining wall

[a] A sufficient missing lemma. Fix some \(2<u<3\). It would suffice to prove that, for every sufficiently large \(x\), every interval immediately below \(x\) of length \(o(x^{1/u})\) contains a semiprime \(rs\) whose two prime factors satisfy

x^{1/u}<r\leq s<x^{1-1/u}.

Indeed, its distance \(h=x-rs\) would be \(o(x^{1/u})<r\), so (2) would hold. The same estimate would give \(F(x)-x\to\infty\).

[c, source-reported] Tao identifies precisely this short-interval semiprime problem. He reports that even on the Riemann hypothesis the available maximal-gap scale is not significantly better than \(O(\sqrt{x}\log x)\), whereas \(x^{1/u}\) has exponent strictly below \(1/2\). Standard sieve methods then encounter the parity barrier, with possible Siegel zeroes creating an additional obstruction. Thus neither the finite computation nor current quoted short-interval machinery supplies the needed uniform lemma.

[c, engineering extrapolation] The finite certificate algorithm examines on the order of \(x/\log^2 x\) balanced semiprimes. Extrapolating its measured \(2.86\times10^7\) heap events in 35 seconds, a Python extension to \(10^{12}\) would require roughly \(2\times10^9\) events, about \(0.7\) core-hours and tens of MB; I did not run it. Even an arbitrarily large finite extension would not address the missing uniform semiprime-gap theorem.

PARTIAL: exactly 100 exceptions are certified for 5 <= n <= 10^10 (last 267680), with an elementary reduction and standalone checker; the uniform semiprime-gap step remains open.

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