mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-06-13, 19:11   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·1,601 Posts
Default Mersenne primes have highly composite p-1?

http://www.mersenneforum.org/showpos...6&postcount=85

Quote:
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.

Alex
http://www.mersenneforum.org/showpos...&postcount=345

Quote:
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.

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
ATH is offline   Reply With Quote
Old 2009-06-13, 20:04   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-06-14, 23:04   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×1,601 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
ATH is offline   Reply With Quote
Old 2009-06-15, 13:11   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×1,601 Posts
Default

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%)
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Factor leaves a C168 Mersenne Composite wblipp ElevenSmooth 7 2013-01-17 02:54
Highly composite polynomials. Arkadiusz Math 5 2012-02-27 14:11
Factoring with Highly Composite Modulus mgb Math 3 2006-09-09 10:35
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00
Mersenne composite using fibonacci TTn Math 5 2002-11-23 03:54

All times are UTC. The time now is 14:39.


Tue Dec 7 14:39:54 UTC 2021 up 137 days, 9:08, 0 users, load averages: 1.28, 1.39, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.