20201007, 14:45  #1 
Einyen
Dec 2003
Denmark
101110100011_{2} Posts 
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 (q1)/2. Each distinct prime factor can be the prime p in k*p and then (q1)/(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 < 10^{9}, which is all there is < 10^{9} since the smallest factor outside GIMPS range would be roughly 2*10^{9}. 2kp+1 with k=1 and p>10^{9}. 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 10^{2} 25 11 4 36.36% 10^{3} 168 80 20 25.00% 10^{4} 1229 603 103 17.08% 10^{5} 9592 4783 583 12.19% 10^{6} 78498 39221 3842 9.80% 10^{7} 664579 332213 26556 7.99% 10^{8} 5761455 2880376 196645 6.83% 10^{9} 50847534 25422922 1511498 5.95% Last fiddled with by ATH on 20201007 at 14:51 
20201007, 15:40  #2 
Jun 2003
12A9_{16} Posts 

20201007, 17:47  #3 
Einyen
Dec 2003
Denmark
3^{2}·331 Posts 
No, the 16 values (mod 120) are more restrictive.
+/ 1 (mod 8) would give 30 values (mod 120): 1 7 9 15 17 23 25 31 33 39 41 47 49 55 57 63 65 71 73 79 81 87 89 95 97 103 105 111 113 119 Last fiddled with by ATH on 20201007 at 17:47 
20201007, 17:47  #4 
Jul 2018
Martin, Slovakia
2·127 Posts 

20201007, 18:02  #5 
Einyen
Dec 2003
Denmark
3^{2}·331 Posts 
You are both correct, the extra 14 values are just the trivial composites mod 3 and mod 5. Did not really think about that, I just always used the 16 values (mod 120), but I could have also used +/ 1 (mod 8).
Good thing I posted in Misc. Math thread then. Last fiddled with by ATH on 20201007 at 18:05 
20201007, 22:19  #6  
Aug 2020
1 Posts 
Quote:


20201009, 10:41  #7 
Romulan Interpreter
Jun 2011
Thailand
21344_{8} Posts 
Mod 120 doesn't bring any benefit compared with mod 60. The next values which bring benefits are 420, 4620, etc (what mfaktX use, they are primorials times 2).
The idea is that mersenne factors are 2kp+1 and 1 or 7 mod 8, so if you want to filter out whole classes, then the total number of classes must be multiple of 4 (so 2kp be multiple of 8). That is why we use 4, 12, 60, 420, 4620, etc. classes. There are some posts on this forum where I put some pari/gp TF code with all those number of classes, shown how much faster is one compared with another, etc., and there were more explanations there. Last fiddled with by LaurV on 20201009 at 10:42 
20201009, 11:09  #8 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·7·11·29 Posts 
Here's a starting point (follow links there)
Pari scripts (fun starts in post #32, then see all discussion after, till the parallelization from Hans, post #118, and the end of the topic). 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factors of Mersenne numbers  bhelmes  Miscellaneous Math  8  20200914 17:36 
Possible values for k (in Mersenne factors)  James Heinrich  Math  127  20190923 06:22 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known Mersenne factors  CRGreathouse  Math  5  20130614 11:44 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 