http://www.mersenneforum.org/showpos...6&postcount=85
Quote:
Originally Posted by akruppa
Maybe there's a simple explanation why Mersenne primes M[I]p[/I] tend to have highly composite p-1. Trivially, 2p-1 and 2p-2 have no common factor, and the latter is 2(2p-1-1) which has a lot of algebraic factors if p-1 is highly composite, and so will have a lot of small prime factors, thus slightly reducing the probability that 2p-1 has small prime factors. The effect can't be very strong, though: divisors of 2p-1 are of form 2kp+1 and few factors of 2p-1-1 will be of this form. Still, it's the only thing I can think of how the number of divisors of p-1 might enter the picture.
If this effect is the reason for the smoother-than-expected p-1 in prime M[I]p[/I], then M[I]p[/I] with smooth p-1should simply have a slightly better chance of surviving trial division, but among the trial-divided candidates, the probability that M[I]p[/I] is prime should be independent of the smoothness of p-1 again.
Alex
|
http://www.mersenneforum.org/showpos...&postcount=345
Quote:
Originally Posted by akruppa
I have no idea how to quantify this. An empirical test is the best I can think of. Only relatively small divisors should be affected, so one might check if those 2[I]p[/I] where p-1 has at least n divisors are more likely to survive trial division to, say, 240.
Alex
|
I took the list from 20M to 30M from the "Factoring limits" list, which is all those that has no known factor below 2^66 (20M) to 2^68 (30M).
There are 587,252 primes from 20M to 30M and of them 369,166 have known factors while 218,086 are in the factoring limit list and have no known factors. I made a small program to test number of factors in p-1 for all 587,252 primes and see if there was a difference:
Code:
p-1 factors A B
---------------------------------------------
2 factors 15617=4.23% 8278=3.80%
3 factors 52822=14.31% 29439=13.50%
4 factors 81916=22.19% 47299=21.69%
5 factors 80449=21.79% 48040=22.03%
6 factors 59649=16.16% 36367=16.68%
7 factors 37016=10.03% 22935=10.51%
8 factors 20575=5.57% 12596=5.78%
9 factors 10774=2,92% 6684=3.06%
10 factors 5394=1.46% 3265=1.50%
11 factors 2571=0.70% 1686=0.77%
12 factors 1280=0.35% 784=0.36%
13 factors 612=0.17% 369=0.17%
14 factors 265=0.07% 169=0.08%
15 factors 127 92
16 factors 57 39
17 factors 28 22
18 factors 7 8
19 factors 5 5
20 factors 0 6
21 factors 1 1
22 factors 1 1
23 factors 1 1
----------------------------------------------
Total 369166(100%) 218086(100%)
Column A are the exponents where 2^p-1 has factors below 2^66-2^68, and B where 2^p-1 have no factors below 2^66-2^68. Looking at the percentages there is no real difference in number of exponents with higher number of factors of p-1 in column B. Maybe we have to check at a lower factor level like 2^40 like Alex suggests.