← All problems

Erdős Problem #1055 — Erdős–Selfridge classification of primes

49 years old · traced to

For a prime pp, let P(p)P(p) be the set of prime divisors of p+1p+1. Define the classes recursively: pp is in class 11 if P(p)⊆{2,3}P(p)\subseteq\{2,3\}. For r≥2r\geq 2, let c(q)c(q) denote the class number of a prime factor qq of p+1p+1; then pp is in class rr if and only if P(p)⊈{2,3}P(p)\not\subseteq\{2,3\} and

max⁡q∈P(p)c(q)=r−1.\max_{q\in P(p)} c(q)=r-1.

This expresses the intended exclusive classification: without the exception excluding class 11, the stated “equality for at least one prime factor” condition would also place class-11 primes in class 22. The recursion is well-defined: for odd pp, each prime divisor of p+1p+1 is smaller than pp, and p=2p=2 is in class 11. Erdős Problem #1055 OEIS Wiki, Erdős–Selfridge classification

For each integer r≥1r\geq1, is the set of primes in class rr infinite? If it is nonempty, write prp_r for its least prime. What is the asymptotic behavior, as r→∞r\to\infty, of pr1/rp_r^{1/r}? Erdős Problem #1055

Background

This is the Erdős–Selfridge classification of primes, posed by Erdős in a 1977 collection of problems. Its recursive rule organizes primes according to the classes of the prime divisors of the neighboring integer p+1p+1: class 11 is the base case, and otherwise the class number is one more than the largest class number among those factors. A related question replaces p+1p+1 by p−1p-1, but that is a distinct variant. Erdős Problem #1055 OEIS Wiki, Erdős–Selfridge classification Erdős (1977)

The two questions probe different aspects of this hierarchy: whether every level occurs infinitely often, and how quickly the least prime at level rr grows on the exponential scale set by the exponent 1/r1/r. Erdős expected pr1/rp_r^{1/r} to tend to infinity; Selfridge thought it quite likely to remain bounded. These are reported expectations, not established conclusions. Erdős Problem #1055

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.