mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-10-07, 14:45   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23×7×53 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 online now   Reply With Quote
Old 2020-10-07, 15:40   #2
axn
 
axn's Avatar
 
Jun 2003

5×23×41 Posts
Default

Quote:
Originally Posted by ATH View Post
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
which can be simplified to q mod 8 = 1 or 7
axn is online now   Reply With Quote
Old 2020-10-07, 17:47   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23×7×53 Posts
Default

Quote:
Originally Posted by axn View Post
which can be simplified to q mod 8 = 1 or 7
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 2020-10-07 at 17:47
ATH is online now   Reply With Quote
Old 2020-10-07, 17:47   #4
Viliam Furik
 
Jul 2018
Martin, Slovakia

22×5×11 Posts
Default

Quote:
Originally Posted by axn View Post
which can be simplified to q mod 8 = 1 or 7
That's true, but using a higher modulo sieves-out little bit more of the composites, such as 9 mod 120.
Viliam Furik is offline   Reply With Quote
Old 2020-10-07, 18:02   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·7·53 Posts
Default

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 2020-10-07 at 18:05
ATH is online now   Reply With Quote
Old 2020-10-07, 22:19   #6
janeandr
 
Aug 2020

1 Posts
Default

Quote:
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.
this kind of math got my brain cooked in a matter of seconds
janeandr is offline   Reply With Quote
Old 2020-10-09, 10:41   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·2,957 Posts
Default

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 2020-10-09 at 10:42
LaurV is offline   Reply With Quote
Old 2020-10-09, 11:09   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·2,957 Posts
Default

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).
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factors of Mersenne numbers bhelmes Miscellaneous Math 8 2020-09-14 17:36
Possible values for k (in Mersenne factors) James Heinrich Math 127 2019-09-23 06:22
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known Mersenne factors CRGreathouse Math 5 2013-06-14 11:44
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 01:55.

Tue Oct 27 01:55:15 UTC 2020 up 46 days, 23:06, 0 users, load averages: 1.49, 1.52, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.