Possible values for k (in Mersenne factors) - Page 8

science_man_88 · 2016-03-14, 14:40

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.

CRGreathouse · 2016-03-14, 15:41

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% ?

CRGreathouse · 2016-03-14, 17:34

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%

GP2 · 2016-05-17, 06:57

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:

Here are the values for k mod 60 instead, again there is non-uniformity:

Code:

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?

LaurV · 2016-05-17, 08:19

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.

GP2 · 2016-05-17, 09:15

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.

LaurV · 2016-05-17, 09:40

Quote:

Originally Posted by GP2

47%

Now that's ~~interesting!~~ funny!

GP2 · 2016-05-17, 10:32

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

bloodIce · 2016-05-17, 12:41

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).

GP2 · 2016-05-17, 17:22

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.

GP2 · 2016-05-17, 18:25

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.

2016-05-17, 06:57	#81
GP2 Sep 2003 2585₁₀ 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, 10:32	#85
GP2 Sep 2003 5·11·47 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, 18:25	#88
GP2 Sep 2003 5·11·47 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
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44
A strange new (?) fact about Mersenne factors	ChriS	Math	14	2006-04-12 17:36
Factors of Mersenne Numbers	asdf	Math	17	2004-07-24 14:00
Factors of Mersenne numbers ?	Fusion_power	Math	13	2003-10-28 20:52

2016-05-17, 08:19	#82
LaurV Romulan Interpreter Jun 2011 Thailand 22613₈ 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, 12:41	#86
bloodIce Feb 2010 Sweden 173 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).