Erdős–Selfridge prime classes: infinitely many primes per class, and growth of $p_r^{1/r}$ (Erdős #1055)
Statement
Consider the following classification of the primes, due to Erdős and Selfridge. A prime $p$ is said to be in class $1$ if the only prime divisors of $p+1$ are $2$ or $3$. Recursively, for $r\geq 2$, a prime $p$ is in class $r$ if every prime factor of $p+1$ lies in some class $\leq r-1$, with at least one prime factor lying in class exactly $r-1$. Two questions. (1) Are there infinitely many primes in each class $r$? (2) If $p_r$ denotes the least prime in class $r$, how does $p_r^{1/r}$ behave as $r\to\infty$ — does it tend to infinity, or remain bounded?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written proof) that there are infinitely many primes in every class $r$, together with a proof determining the asymptotic behaviour of $p_r^{1/r}$ — either $p_r^{1/r}\to\infty$ (Erdős) or $p_r^{1/r}$ bounded (Selfridge). ADVANCES: extend the verified sequence $p_r$ of least primes in class $r$ (OEIS A005113) beyond its currently known terms, with the search program and a reproducible certificate that each new $p_r$ is genuinely the least prime whose $p+1$ has the required recursive class structure (and that no smaller prime qualifies); prove infinitude of primes for a specific new class $r$; or establish rigorous bounds on $p_r$ as a function of $r$ that constrain $p_r^{1/r}$ (a one-sided unconditional bound settling boundedness or unboundedness in part). Deliver the proof, or the class-certifying search code plus the extended sequence and its exhaustiveness certificate.
Background
A classification introduced by Erdős and Selfridge [Er77]; listed as open on erdosproblems.com/1055 (fetched 2026-07-21, status 'open'). It is not hard to show that the number of primes $\leq n$ in any fixed class $r$ is $n^{o(1)}$. The sequence of least primes $p_r$ begins $2,13,37,73,1021,\ldots$ (OEIS A005113). Erdős conjectured $p_r^{1/r}\to\infty$, whereas Selfridge thought it quite likely that $p_r^{1/r}$ stays bounded — the two competing beliefs are on record and remain undecided. The same classification and questions can be posed with $p+1$ replaced by $p-1$. The problem is A18 in Guy's 'Unsolved Problems in Number Theory' [Gu04]; no cash prize is attached. Attacker's tool: exact computation extending the least-prime sequence $p_r$ (A005113) to new records — for each candidate prime, factor $p+1$ and recursively certify the class of every prime factor — together with counts of primes by class up to large bounds to test whether $p_r^{1/r}$ grows.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1055 (T. F. Bloom) | website |
| REF-02 | OEIS A005113 — least prime in the r-th Erdős–Selfridge class | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.