Erdős Problem #1055 — Erdős–Selfridge classification of primes
For a prime , let be the set of prime divisors of . Define the classes recursively: is in class if . For , let denote the class number of a prime factor of ; then is in class if and only if and
This expresses the intended exclusive classification: without the exception excluding class , the stated “equality for at least one prime factor” condition would also place class- primes in class . The recursion is well-defined: for odd , each prime divisor of is smaller than , and is in class . Erdős Problem #1055 OEIS Wiki, Erdős–Selfridge classification
For each integer , is the set of primes in class infinite? If it is nonempty, write for its least prime. What is the asymptotic behavior, as , of ? 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 : class is the base case, and otherwise the class number is one more than the largest class number among those factors. A related question replaces by , 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 grows on the exponential scale set by the exponent . Erdős expected to tend to infinity; Selfridge thought it quite likely to remain bounded. These are reported expectations, not established conclusions. Erdős Problem #1055
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.