View Single Post
Old 2020-10-07, 14:45   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·331 Posts
Default Mersenne factors 2*k*p+1

All primes q>3 can be written on the form q=2*k*p + 1 for some k>0 and some prime p, and many primes q can be written like that in several different ways.
The number of different ways is the number of the distinct prime factors of (q-1)/2. Each distinct prime factor can be the prime p in k*p and then (q-1)/(2*p) is the k value.

Not all primes q=2kp+1 is the factor of a Mersenne number with prime exponent p, and those that are a factor, can only be the factor of 1 Mersenne number.

To be a factor the prime q (mod 120) must be equal to one of these 16 values:
1 7 17 23 31 41 47 49 71 73 79 89 97 103 113 119
Close to half of all primes satisfies this requirement but not all of those are factors. I was curious how many of those are Mersenne factors. I checked all factors in the GIMPS database < 109, which is all there is < 109 since the smallest factor outside GIMPS range would be roughly 2*109. 2kp+1 with k=1 and p>109.

Here is the data, the primes%120 column is the number of primes satisfying the mod 120 requirements. I included the 6 Mersenne primes: M3=7, M5=31, M7=127, M13=8191, M17=131071, M19=524287 in the Mersenne factors column since they are really their own factors.

Not surprisingly the ratio of Mersenne factors to primes goes down with size. The percentages are the ratio of Mersenne factors to the primes%120 column.

Code:
n	Total primes	primes%120	Mersenne factors
102	25		11		4		36.36%
103	168		80		20		25.00%
104	1229		603		103		17.08%
105	9592		4783		583		12.19%
106	78498		39221		3842		9.80%
107	664579		332213		26556		7.99%
108	5761455		2880376		196645		6.83%
109	50847534	25422922	1511498		5.95%

Last fiddled with by ATH on 2020-10-07 at 14:51
ATH is offline   Reply With Quote