mersenneforum.org > Math Possible values for k (in Mersenne factors)
 Register FAQ Search Today's Posts Mark Forums Read

2016-03-14, 14:40   #78
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

Quote:
 Originally Posted by PawnProver44 I am not trolling you. This is common logic I am using here.
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 2016-03-14 at 14:51

2016-03-14, 15:41   #79
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by PawnProver44 About 9.4% of all odd primes are cofactors of Mersenne Numbers with p prime for 2^p-1.
Are you saying that the density of
https://oeis.org/A122094
in the primes is about 9.4% ?

2016-03-14, 17:34   #80
CRGreathouse

Aug 2006

5,987 Posts

Quote:
Originally Posted by LaurV
Quote:
 Originally Posted by PawnProver44 About 9.4% of all odd primes are cofactors of Mersenne Numbers with p prime for 2^p-1.
Wrong.

Edit: you have 2 factors in 4 primes, below 10 (3 and 7 divide respectively M2 and M3), so 50%.
Under 100, you have 24 odd primes, from which 6 are factors (additional of the above, 23, 31, 47, 89, divide respectively M11, M5, M23, M11). So 25%.
Continuing, with primes under 10^3 you have 22/167=13.1736%
with primes under 10^4 you have 106/1228=8.6319%
with primes under 10^5 you have 386/9591=6.1099%
with primes under 10^6 you have 3846/78497=4.8996%
etc.
I concur with your numbers. To continue:
10^7 gives 3.9967%
10^8 gives 3.4132%
10^9 gives 2.9726%
10^10 gives 2.6332%

 2016-05-17, 06:57 #81 GP2     Sep 2003 1010000110112 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 From cursory inspection of the histograms there are large spikes at k ≡ 0 (mod 12), and k ≡ 3,4,8,9 (mod 12) occur more often than 1,5,7,11 (mod 12), and of course k ≡ 2,6,10 (mod 12) are impossible. 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 Here are the values for k mod 60 instead, again there is non-uniformity: 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 I wonder if you did the histogram for k mod 4620, would it still be non-uniform? 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 2016-05-17 at 07:11
 2016-05-17, 08:19 #82 LaurV 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.
2016-05-17, 09:15   #83
GP2

Sep 2003

13·199 Posts

Quote:
 Originally Posted by LaurV 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.
Actually, my table shows empirically that k ≡ 0 (mod 4) occurs at slightly less than 50%. (I wonder if there is some mathematical explanation for this).

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
Between 10M and 20M:

Code:
 Count k
----- -
267867 0     47.08%
157183 1
143908 3
Between 20M and 30M:

Code:
 Count k
----- -
252636 0     46.94%
148030 1
137546 3
Between 30M and 40M:

Code:
 Count k
----- -
247361 0     47.07%
144649 1
133538 3
Between 40M and 50M:

Code:
 Count k
----- -
241768 0     47.07%
141969 1
129859 3
Between 50M and 60M:

Code:
 Count k
----- -
239206 0     47.14%
139458 1
128745 3
Between 60M and 70M:

Code:
 Count k
----- -
236102 0     47.08%
137889 1
127449 3
... and so forth. The effect is consistent and would appear to be statistically significant.

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 non-zero 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 2016-05-17 at 09:31

2016-05-17, 09:40   #84
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

2·47·109 Posts

Quote:
 Originally Posted by GP2 47%
Now that's interesting! funny!

 2016-05-17, 10:32 #85 GP2     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 Between 10M and 20M: Code:  Count p, k ----- ---- 133866 1, 0 48.2% 143908 1, 3 134001 3, 0 46.0% 157183 3, 1
 2016-05-17, 12:41 #86 bloodIce     Feb 2010 Sweden AD16 Posts GP2, could you check 900M-906M 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).
2016-05-17, 17:22   #87
GP2

Sep 2003

13×199 Posts

Quote:
 Originally Posted by bloodIce GP2, could you check 900M-906M range?
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
It's not exactly the range you asked for but hopefully close enough.

Note that this uses the list of factors retrieved from mersenne.org, and that data doesn't include the largest factor of fully-factored 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 2016-05-17 at 17:31

 2016-05-17, 18:25 #88 GP2     Sep 2003 50338 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 As before, this does not include highest factors of fully-factored Mersenne numbers, since these are not provided by the PrimeNet data, but only a vanishingly small fraction of Mersenne numbers are fully factored.

 Similar Threads Thread Thread Starter Forum Replies Last Post tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44 ChriS Math 14 2006-04-12 17:36 asdf Math 17 2004-07-24 14:00 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 12:09.

Mon Dec 5 12:09:14 UTC 2022 up 109 days, 9:37, 0 users, load averages: 1.27, 0.94, 0.87