20160314, 14:40  #78 
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
here's another piece of information for you then ( I can't find the thread where this was discussed with prime95 maybe I did some of it by PM) if two numbers in an arithmetic progression like 2kp+1 have k values that are separated by a multiple of r then either both don't divide by r or both do. can you at least prove this true ? oh and common logic doesn't always work as mathematical logic.
Last fiddled with by science_man_88 on 20160314 at 14:51 
20160314, 15:41  #79  
Aug 2006
5,987 Posts 
Quote:
https://oeis.org/A122094 in the primes is about 9.4% ? 

20160314, 17:34  #80  
Aug 2006
5,987 Posts 
Quote:
10^7 gives 3.9967% 10^8 gives 3.4132% 10^9 gives 2.9726% 10^10 gives 2.6332% 

20160517, 06:57  #81 
Sep 2003
101000011011_{2} Posts 
Getting back to the original question that started this thread...
For fun I looked at histograms of values of k for known factors 2kp+1 of Mersenne numbers. As expected, values where k ≡ 2 (mod 4) are not present since they are mathematically impossible. For the rest, k ≡ 0 occurs more often than 1 or 3. Here are the values of k mod 4 for known factors of Mersenne numbers with exponent less than 10M: Code:
Count k   336365 0 196835 1 181578 3 Here are the values of k mod 12 for known factors of Mersenne numbers with exponent less than 10M: Code:
Count k   161015 0 68043 1 97655 3 91201 4 45934 5 43282 7 84149 8 82858 9 40641 11 Code:
Count k   36871 0 34830 1 31479 3 26387 4 16185 5 11108 7 19873 8 19031 9 9162 11 35370 12 8905 13 22374 15 16623 16 8224 17 8071 19 21353 20 16039 21 7777 23 30987 24 10004 25 15354 27 15221 28 7463 29 7514 31 14647 32 14783 33 9822 35 29112 36 7251 37 14276 39 19021 40 7101 41 7129 43 14101 44 19210 45 6936 47 28675 48 7053 49 14172 51 13949 52 6961 53 9460 55 14175 56 13795 57 6944 59 When you whittle the 4620 equivalence classes down to 960, are all 960 equally likely to produce factors? In LaurV's example, where you are left with classes 0, 3, 8, 11, 15, 20, 24, 35, 36, etc., would you just sequentially test the 0 class, then the 3 class, then the 8 class, etc. or would it make sense to test the different classes according to some priority ranking? Last fiddled with by GP2 on 20160517 at 07:11 
20160517, 08:19  #82 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 
There is no "priority ranking". Their chances, for a given p, are equal. Your fallacy comes from considering all p. For example, if p=1 (mod 4) then k can be 0 or 3 (mod 4). In equal proportions. If p=3 (mod 4) then k can be 0 or 1 (mod 4). In equal proportions.
When you combine both, i.e. for all p prime, k can be 0 mod 4 with a 50% chance, 1 mod 4 with 25% chance, and 3 mod 4 with 25% chance, what your table shows. But given a p, we can't establish a "hierarchy" of the classes (order to be tested) unless we know the factors first. 
20160517, 09:15  #83  
Sep 2003
13·199 Posts 
Quote:
For known factors of Mersenne numbers with prime exponent between 0M and 10M (as of May 1 2016): Code:
Count k   336365 0 47.06% 196835 1 181578 3 Code:
Count k   267867 0 47.08% 157183 1 143908 3 Code:
Count k   252636 0 46.94% 148030 1 137546 3 Code:
Count k   247361 0 47.07% 144649 1 133538 3 Code:
Count k   241768 0 47.07% 141969 1 129859 3 Code:
Count k   239206 0 47.14% 139458 1 128745 3 Code:
Count k   236102 0 47.08% 137889 1 127449 3 So if we were doing a very simplistic filtering with only 4 classes instead of 4620, and only filtering out k ≡ 2 (mod 4), then it appears empirically that we should test the nonzero k values before the zero, for a small percentage speedup. So perhaps there would be a similar effect with 60 classes or 4620 classes, with a small efficiency gain. Last fiddled with by GP2 on 20160517 at 09:31 

20160517, 09:40  #84 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·47·109 Posts 

20160517, 10:32  #85 
Sep 2003
13×199 Posts 
Here is a further breakdown of both p mod 4 and k mod 4:
For known factors of Mersenne numbers with prime exponent between 0M and 10M (as of May 1 2016): Code:
Count p, k   168302 1, 0 48.1% 181578 1, 3 168063 3, 0 46.1% 196835 3, 1 Code:
Count p, k   133866 1, 0 48.2% 143908 1, 3 134001 3, 0 46.0% 157183 3, 1 
20160517, 12:41  #86 
Feb 2010
Sweden
AD_{16} Posts 
GP2, could you check 900M906M range? All of it is factored to TF64 for all exponents. There is only trial factoring done, so there are no Pm1 and ECM factors there. Of course not a single exponent there is fully factored (or at least we do not know yet).

20160517, 17:22  #87 
Sep 2003
13×199 Posts 
p mod 4 and k mod 4, for known (as of May 17 2016 00:00) factors 2kp+1 of Mersenne numbers with prime exponents between 900M and 910M:
Code:
Count p, k   83738 1, 0 47.9% 91053 1, 3 84257 3, 0 45.9% 99410 3, 1 Note that this uses the list of factors retrieved from mersenne.org, and that data doesn't include the largest factor of fullyfactored exponents. So for instance for M11 we include 23 as a factor but not 89. However only a very tiny fraction of exponents are fully factored, mostly for very small exponents, so this shouldn't make any difference. Last fiddled with by GP2 on 20160517 at 17:31 
20160517, 18:25  #88 
Sep 2003
5033_{8} Posts 
In case anyone cares here are some stats for modulo 12:
p mod 12, k mod 12 for known (as of May 1 2016 00:00) factors of Mersenne numbers with prime exponent between 0M and 100M: Code:
Count p, k   297308 1, 0 362309 1, 3 313080 1, 8 302897 1, 11 296577 5, 0 361252 5, 3 339723 5, 4 318230 5, 7 298098 7, 0 340619 7, 5 311989 7, 8 307683 7, 9 295166 11, 0 506521 11, 1 339286 11, 4 304830 11, 9 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known Mersenne factors  CRGreathouse  Math  5  20130614 11:44 
A strange new (?) fact about Mersenne factors  ChriS  Math  14  20060412 17:36 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 