mersenneforum.org > Math Mersenne primes have highly composite p-1?
 Register FAQ Search Today's Posts Mark Forums Read

2009-06-13, 19:11   #1
ATH
Einyen

Dec 2003
Denmark

2·7·227 Posts
Mersenne primes have highly composite p-1?

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.

Last fiddled with by ATH on 2009-06-13 at 19:19

 2009-06-13, 20:04 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts I rearranged a little to show the survival rate of exponents p depending on the number of factors of p-1: Code: p-1 factors #p #survivors #suvival rate ----------------------------------------------------- 2 factors 23895 8278 0.346 3 factors 82261 29439 0.358 4 factors 129215 47299 0.366 5 factors 128489 48040 0.374 6 factors 96016 36367 0.379 7 factors 59951 22935 0.383 8 factors 33171 12596 0.380 9 factors 17458 6684 0.383 10 factors 8659 3265 0.377 11 factors 4257 1686 0.396 12 factors 2064 784 0.380 13 factors 981 369 0.376 14 factors 434 169 0.389 So it looks like those p with few factors in p-1 do, in fact, have a lower chance of surviving trial division. ATH, I assume the number of factors is the number of prime factors with multiplicity in p-1? It might be interesting to make such a table for the number of proper divisors of p-1 as well. My hypothesis isn't very convincing, though. By the same argument, 2[I]p[/I]-4 and 2[I]p[/I]-1 have at most the factor 3 in common, so the number of divisors in p-2 (and p-3 and p-4 etc.) should also affect the probability that Mp is prime. Alex
2009-06-14, 23:04   #3
ATH
Einyen

Dec 2003
Denmark

C6A16 Posts

Quote:
 Originally Posted by akruppa So it looks like those p with few factors in p-1 do, in fact, have a lower chance of surviving trial division. ATH, I assume the number of factors is the number of prime factors with multiplicity in p-1? It might be interesting to make such a table for the number of proper divisors of p-1 as well.
If you mean distinct prime factors, here is the list:
Code:
p-1 factors	Total(20M-30M)	numbers without factors to 2^66-2^68
--------------------------------------------------------------------
2 factors	49855		17960 = 36.02%
3 factors	173824		63988 = 36.81%
4 factors	218645		81127 = 37.10%
5 factors	118143		44684 = 37.83%
6 factors	25228		9692  = 38.42%
7 factors	1548		629   = 40.63%
8 factors	9		6     (=66.67%)
--------------------------------------------------------------------
Total		587252		218086
There is a clear rising percentage of numbers "surviving" trialfactor to 2^66-2^68, the more distinct prime factors p-1 has.

If you mean all factors (not just prime factors) then the list is extensive, here is whole list (not counting 1 and p-1 as factors of p-1): mersennetest.txt

Here is the list abbriviated by combining the factor-categories with low number of members in them:
Code:
p-1 factors	Total(20M-30M)	numbers without factors to 2^66-2^68
--------------------------------------------------------------------
2 factors	23895		8278 = 34.64%
4 factors	12264		4577 = 37.32%
6 factors	76473		27329 = 35.74%
7-8 factors	3355		1230 = 36.66%
10 factors	47504		17911 = 37.70%
12-13 factors	985		376 = 38.17%
14 factors	98842		35686 = 36,10%
16 factors	5377		2038 = 37.90%
18 factors	10600		3991 = 37.65%
19-22 factors	68947		25980 = 37.68%
23-26 factors	2651		946 = 35.68%
28 factors	1955		753 = 38.52%
30 factors	66115		24718 = 37.39%
31-34 factors	13651		5150 = 37.73%
36-38 factors	12384		4728 = 38,18%
40-46 factors	49363		18813 = 38.11%
48-54 factors	3795		1435 = 37.81%
58 factors	4090		1563 = 38.22%
61-62 factors	24317		9256 = 38.06%
64-70 factors	12353		4747 = 38.43%
73-78 factors	6840		2622 = 38.33%
79-94 factors	18451		6969 = 37.77%
96-106 factors	1528		577 = 37.76%
108-110 factors	1234		465 = 37.68%
118 factors	2806		1091 = 38.88%
124-126 factors	4652		1819 = 39.10%
128-142 factors	4558		1761 = 38.64%
148-158 factors	1635		634 = 38.78%
160-178 factors	951		361 = 37.96%
180-190 factors	2707		1076 = 39.75%
194-214 factors	659		272 = 41.27%
218-254 factors	1294		508 = 39.26%
258-286 factors	546		230 = 42.12%
292-318 factors	147		58 = 39.46%
322-358 factors	141		57 = 40.43%
376-382 factors	108		43 = 39.81%
394-430 factors	48		28 = 58.33%
446-478 factors	20		7 = 35.00%
502-574 factors	11		3 = 27.27%
--------------------------------------------------------------------
Total		587252		218086 (=37.14%)
The trend is not so clear here, since there is so many categories with more or less members in. But 39+% happens only for >124 factors and 40+% only for >194factors.

Last fiddled with by ATH on 2009-06-14 at 23:11

 2009-06-15, 13:11 #4 ATH Einyen     Dec 2003 Denmark 2×7×227 Posts Combined the categories on the last list even more (the one with all factors of p-1 except 1 and p-1): Code: p-1 factors Total(20M-30M) numbers without factors to 2^66-2^68 -------------------------------------------------------------------- 2-6 factors 112632 40184 = 35.68% 7-13 factors 51844 19517 = 37.65% 14-18 factors 114819 41715 = 36.33% 19-22 factors 68947 25980 = 37.68% 23-30 factors 70721 26417 = 37.35% 31-46 factors 75398 28691 = 38.05% 48-62 factors 32202 12254 = 38.05% 64-94 factors 37644 14338 = 38.09% 96-142 factors 14778 5713 = 38.66% 148-254 factors 7246 2851 = 39.35% 258-382 factors 942 388 = 41.19% 394-574 factors 79 38 = 48.10% -------------------------------------------------------------------- Total 587252 218086 (=37.14%)

 Similar Threads Thread Thread Starter Forum Replies Last Post wblipp ElevenSmooth 7 2013-01-17 02:54 Arkadiusz Math 5 2012-02-27 14:11 mgb Math 3 2006-09-09 10:35 philmoore Factoring 21 2004-11-18 20:00 TTn Math 5 2002-11-23 03:54

All times are UTC. The time now is 17:46.

Wed Oct 27 17:46:07 UTC 2021 up 96 days, 12:15, 0 users, load averages: 0.91, 1.09, 1.08