View Single Post
Old 2009-06-13, 19:11   #1
ATH's Avatar
Dec 2003

3,313 Posts
Default Mersenne primes have highly composite p-1?

Originally Posted by akruppa View Post
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.


Originally Posted by akruppa View Post
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.


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:

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.

Last fiddled with by ATH on 2009-06-13 at 19:19
ATH is offline   Reply With Quote