mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-03-14, 14:40   #78
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-03-14, 15:41   #79
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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 is offline   Reply With Quote
Old 2016-03-14, 17:34   #80
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by LaurV View Post
Quote:
Originally Posted by PawnProver44 View Post
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%
CRGreathouse is offline   Reply With Quote
Old 2016-05-17, 06:57   #81
GP2
 
GP2's Avatar
 
Sep 2003

1010000110112 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2016-05-17, 08:19   #82
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2016-05-17, 09:15   #83
GP2
 
GP2's Avatar
 
Sep 2003

13·199 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
GP2 is offline   Reply With Quote
Old 2016-05-17, 09:40   #84
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

Quote:
Originally Posted by GP2 View Post
47%
Now that's interesting! funny!
LaurV is offline   Reply With Quote
Old 2016-05-17, 10:32   #85
GP2
 
GP2's Avatar
 
Sep 2003

13×199 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2016-05-17, 12:41   #86
bloodIce
 
bloodIce's Avatar
 
Feb 2010
Sweden

AD16 Posts
Default

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).
bloodIce is offline   Reply With Quote
Old 2016-05-17, 17:22   #87
GP2
 
GP2's Avatar
 
Sep 2003

13×199 Posts
Default

Quote:
Originally Posted by bloodIce View Post
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
GP2 is offline   Reply With Quote
Old 2016-05-17, 18:25   #88
GP2
 
GP2's Avatar
 
Sep 2003

50338 Posts
Default

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

Thread Tools


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

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

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔