Erdős Problem #430
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
Fix an integer \(n\). Start with \(a_1=n-1\), then construct a decreasing sequence of positive integers. At each step choose the largest smaller integer \(a\) for which every prime factor of \(a\) is greater than \(n-a\). For example, the prime factors of \(21\) are \(3\) and \(7\); if \(n-a=1\), both are greater than the required threshold.
Erdős Problem 430 asks whether, for every sufficiently large \(n\), some number in this decreasing sequence must be composite, rather than all selected numbers being prime. The question is one of eventual necessity, not of what happens at one specific \(n\). A finite computation can find examples in both directions without resolving this statement.
There is a small but important convention: the maintained statement describes a sequence in \([1,n)\), while its example for \(n=8\) stops after \(7\) and \(5\). If \(1\) were included literally, the prime-factor condition would hold vacuously because \(1\) has no prime factors, and \(1\) itself would not be prime. The intended nontrivial problem therefore treats \(1\) as excluded from the list of potential prime or composite entries. Any formal normalization must make this convention explicit.
A small example
For \(n=8\), the first selected value is \(a_1=7\), whose prime factor \(7\) is greater than \(8-7=1\). The next qualifying value is \(5\), because its prime factor \(5\) exceeds \(8-5=3\). The integer \(6=2\cdot3\) fails since its prime factor \(2\) is not greater than \(8-6=2\); the values \(4,3,2\) also fail their strict inequalities. Thus the nontrivial sequence is
and it consists only of primes. This reproduces the example on the maintained problem page.
The same exact factorization test gives, for \(n=20\),
again all primes. These finite exceptions do not contradict a conjecture about all sufficiently large \(n\), since the required threshold might be far larger. On the other hand, for \(n=22\) the very first term is \(21=3\cdot7\), a composite number with threshold \(22-21=1\), so it is an immediate composite witness.
A reproducible finite algorithm simply checks every integer \(m\) from \(n-1\) down to \(2\), factors \(m\) exactly, and includes it if its smallest prime factor satisfies
Here \(P^-(m)\) is the least prime factor of \(m\). Since every other prime factor is at least as large, checking only the smallest factor is equivalent to checking all prime factors. This reduces the rule to an ordinary exact integer inequality.
What is known
The question appears in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), in the historical scanned monograph. Erdős and Graham described preliminary numerical calculations made by Selfridge suggesting an affirmative answer, while stating that no proof was then known. The numerical report is historical evidence, not a theorem.
The maintained Erdős Problems #430 page still labels the statement OPEN. It credits Sarosh Adenwalla with an equivalence to the first part of Problem #385. The static form is easier to state than the decreasing algorithm: for every sufficiently large \(n\), does there exist some composite \(m<n\) whose prime factors all exceed \(n-m\)?
Why is this equivalent? The greedy sequence lists qualifying numbers in descending order, with no further condition depending on the previously selected terms beyond being smaller. If a qualifying composite \(m\) exists, it must appear when the algorithm reaches its position. Conversely, if the algorithm selects a composite, that number is a qualifying \(m\) in the static formulation. This equivalence depends on using the same range, especially excluding the vacuously qualifying value \(1\).
The source reports no published theorem settling the eventual-existence question. Related results about smooth or rough integers may provide research tools, but they do not by themselves imply the exact composite witness required here. It would be a mistake to interpret the early all-prime examples as disproving eventual truth, or the occasional composite witnesses as proving it.
GCL's current state
The original GCL source issue #1700 pins the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml with Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its status is open, consistent with the currently maintained entry.
The protected issue also states that no 430.lean file exists in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. This is a precise source-provenance boundary. A newer formal source, if found, would need a separate commit and semantic review, particularly because of the issue of whether the value \(1\) belongs to the sequence.
The authenticated source audit is original issue #1700, RESULT/1 comment #6157433586. It records a bounded task and the source conventions but does not certify a solution or constitute protected V2 editorial admission.
What remains
A suitable next task is an exact computational audit over the bounded domain \(3\leq n\leq5000\). Use both a sieve of smallest prime factors and independent trial division to enumerate all qualifying numbers \(2\leq m<n\). Record which inputs give an all-prime sequence and, for every other input, the largest qualifying composite. Verify the hand calculations at \(n=8\), \(20\) and \(22\).
The mathematical source task is to read the first part of Problem #385 and write a proof that its quantified static statement is equivalent to Problem #430 under identical domain conventions. In particular, show why the strict inequality for the least prime factor suffices, and specify how the value \(1\) is handled. The bounded task succeeds if two independent computations agree and the statement mapping is exact; it fails upon an incorrect prime factor, an off-by-one inequality or a claim that finite results settle eventual truth. Stop after this computational and source-concordance audit, keeping the original problem open.
Sources and claim boundaries
Historical question: Erdős–Graham (1980). Current statement and Selfridge's reported numerical observation: Erdős Problem #430. Related equivalence: Problem #385. Protected provenance: GCL source issue #1700, the frozen catalogue, and the authenticated RESULT/1 comment.
The example sequences and least-prime-factor normalization are independently verifiable elementary claims. Selfridge's calculations are reported background, not a proof. The asymptotic conjecture remains open, no pinned Lean proof is asserted, and editorial acceptance is determined separately.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1700 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.