Problem Statement
A prime $p$ is in class $1$ if the only prime divisors of $p+1$ are $2$ or $3$. In general, a prime $p$ is in class $r$ if every prime factor of $p+1$ is in some class $\leq r-1$, with equality for at least one prime factor.
Are there infinitely many primes in each class? If $p_r$ is the least prime in class $r$, then how does $p_r^{1/r}$ behave?
Are there infinitely many primes in each class? If $p_r$ is the least prime in class $r$, then how does $p_r^{1/r}$ behave?
Categories:
Number Theory Primes
Progress
A classification due to Erdős and Selfridge. It is easy to prove that the number of primes $\leq n$ in class $r$ is at most $n^{o(1)}$.The sequence $p_r$ begins $2,13,37,73,1021$ (A005113 in the OEIS). Erdős thought $p_r^{1/r}\to \infty$, while Selfridge thought it quite likely to be bounded.
A similar question can be asked replacing $p+1$ with $p-1$.
This is problem A18 in Guy's collection [Gu04].
Source: erdosproblems.com/1055 | Last verified: January 19, 2026