Erdős Problem #1055
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, primes.
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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Take any prime \(p\) and factor \(p+1\) into primes. Erdős and Selfridge proposed a recursive way of assigning \(p\) to a class. It lies in class 1 if all prime factors of \(p+1\) are \(2\) or \(3\). Otherwise, its class is one greater than the largest class of any prime factor of \(p+1\).
Erdős Problem #1055 asks whether there are infinitely many primes in every fixed class, not merely whether the first few classes are populated. It also asks how quickly the least prime \(p_r\) of class \(r\) grows. Erdős suspected that
Selfridge suspected instead that this root might remain bounded. These are competing conjectural expectations.
A small example
Since \(7+1=2^3\), the prime \(7\) has class 1. Since \(13+1=2\cdot7\), the prime \(13\) has class 2. Next, \(19+1=2^2\cdot5\); since \(5+1=2\cdot3\), the prime \(5\) has class 1, hence \(19\) has class 2. Therefore
puts \(37\) in class 3, and \(73+1=2\cdot37\) puts \(73\) in class 4. Finally, \(1021+1=2\cdot7\cdot73\) puts \(1021\) in class 5. The primality and factorizations in this chain were independently checked.
A separate exact computation now enumerates all 303 primes up to 2,000 using two independent class-rank algorithms. They agree on every tested prime and establish that \(2,13,37,73,1021\) really are the smallest primes in classes 1 through 5. This is a finite classification, not proof that every higher class is populated.
What is known
The canonical catalogue records the problem as open and lists the initial least representatives \(2,13,37,73,1021\). It also reports that the number of class‑\(r\) primes up to \(x\) is at most \(x^{o(1)}\) for each fixed \(r\). Such a sparsity statement is compatible with both finite and infinite classes: it does not resolve the infinitude question.
The historical sources include Erdős's earlier discussion and Guy, Unsolved Problems in Number Theory, problem A18. Their exact printed statements and page-level bibliography have not been independently checked in this review.
GCL's current state
Source audit #2326 verifies a chain of finite prime-class assignments and inspects the frozen Lean source.
The Lean file describes the recursive class definition and the infinitude and asymptotic conjectures. Crucially, its declaration asserting a prime exists in every class has an unproved placeholder; subsequent definitions of least representatives depend on it. Neither the file's existence nor its metadata independently establishes these conjectures.
What remains
The historical question requires either a proof that each class contains infinitely many primes or a counterexample, plus a determination of how the least representatives grow. As a bounded source and formalization audit, GCL can first compare the exact historic recursion with the frozen Lean definition, retain the independently reproduced finite-rank checks and verify the historic source statements. Finite computations alone cannot establish the asymptotic results.
Sources and claim boundaries
- Erdős Problem #1055, historical problem statement and status.
- OEIS A005113, reported least representatives, for finite cross-checking only.
- Frozen formal-conjectures file, statements with unresolved proofs.
- Finite arithmetic verification program, 303 primes cross-checked by two algorithms.
- Authenticated GCL source return #2326, partial source audit, not mathematical proof certification or editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2326 — 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.