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

2016-05-17, 18:37   #89
GP2

Sep 2003

5·11·47 Posts

Quote:
 Originally Posted by GP2 It's not exactly the range you asked for but hopefully close enough.
In case the exact range mattered (greater than 900M and less than 906M), it's the same pattern:

Code:
Count p, k
----- ----
51071 1, 0     48.2%
54982 1, 3

51388 3, 0     46.0%
60254 3, 1

 2016-05-17, 20:21 #90 bloodIce     Feb 2010 Sweden 173 Posts Thank you very much, GP2! The range actually mattered. I am pretty sure that all exponents are "combed" to TF64, but of course some are factored to higher levels. It tells me, that the small factors appear in the proportions you mentioned. It seems that k ≡ 0 (mod 4) is under-represented and k ≡ 1 (mod 4) is over-represented (no matter in which range). The question is why?
2016-05-17, 20:28   #91
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by bloodIce The question is why?
a thought I just had was that we know that if one value of k divides by a prime it will be less than that prime k=0 is alway producing 2*k*p+1 =1 which doesn't divide by any primes so every 2*primorial number of k can't divide by most of those primes either. because the number of 2*primorial is always 0 mod 4 there may be infinitely many that survive more eliminations than others ?

 2016-05-18, 00:17 #92 GP2     Sep 2003 50318 Posts Modulo 60: p mod 60, k mod 60 for all known (as of May 17 2016 00:00) factors of Mersenne numbers with prime exponent between 0M and 1000M, i.e. all factors known to PrimeNet: Code:  Count p, k ----- ---- 124649 1, 0 300409 1, 3 186317 1, 8 172879 1, 11 155089 1, 15 145928 1, 20 144067 1, 23 141571 1, 24 136090 1, 35 133215 1, 36 132569 1, 39 130190 1, 44 127830 1, 48 127812 1, 51 127818 1, 56 125948 1, 59 124644 7, 0 227009 7, 5 186684 7, 8 178561 7, 9 164620 7, 12 153731 7, 17 145996 7, 20 141909 7, 24 137322 7, 29 135529 7, 32 135658 7, 33 131437 7, 44 131008 7, 45 128428 7, 48 127181 7, 53 126903 7, 57 123202 11, 0 675098 11, 1 251618 11, 4 177744 11, 9 162659 11, 13 151482 11, 16 147363 11, 21 140917 11, 24 138911 11, 25 138968 11, 28 134721 11, 33 131311 11, 36 129662 11, 40 128642 11, 45 126984 11, 48 128823 11, 49 124727 13, 0 300320 13, 3 186332 13, 8 172406 13, 11 164678 13, 12 155378 13, 15 145789 13, 20 143745 13, 23 138817 13, 27 134869 13, 32 136945 13, 35 132949 13, 36 128590 13, 47 128247 13, 48 127779 13, 51 127570 13, 56 124179 17, 0 299488 17, 3 253302 17, 4 209809 17, 7 163192 17, 12 154335 17, 15 148650 17, 19 141413 17, 24 138284 17, 27 140983 17, 28 132398 17, 39 130277 17, 40 129479 17, 43 128032 17, 48 128120 17, 52 126975 17, 55 125375 19, 0 227215 19, 5 179123 19, 9 164243 19, 12 154732 19, 17 146699 19, 20 148587 19, 21 141662 19, 24 138276 19, 29 135206 19, 32 133402 19, 36 131338 19, 41 130949 19, 44 130076 19, 45 128189 19, 56 126688 19, 57 123621 23, 0 675780 23, 1 162527 23, 12 163840 23, 13 151718 23, 16 147972 23, 21 139434 23, 25 140612 23, 28 135011 23, 33 132032 23, 36 131022 23, 37 129451 23, 40 128905 23, 45 127362 23, 48 127295 23, 52 124853 23, 57 124704 29, 0 253873 29, 4 209818 29, 7 163884 29, 12 154580 29, 15 152890 29, 16 148840 29, 19 142200 29, 24 138804 29, 27 137359 29, 31 133079 29, 36 132748 29, 39 130908 29, 40 128772 29, 51 128364 29, 52 127108 29, 55 124157 31, 0 226979 31, 5 186790 31, 8 179296 31, 9 146734 31, 20 149477 31, 21 142546 31, 24 137365 31, 29 135759 31, 33 133434 31, 36 131489 31, 41 131731 31, 44 130143 31, 45 128597 31, 48 126666 31, 53 127865 31, 56 124666 37, 0 300367 37, 3 186716 37, 8 163732 37, 12 154975 37, 15 145916 37, 20 143783 37, 23 141923 37, 24 138743 37, 27 135598 37, 32 136199 37, 35 132697 37, 39 131752 37, 44 128633 37, 47 128414 37, 48 126488 37, 59 124147 41, 0 300141 41, 3 252836 41, 4 154027 41, 15 152853 41, 16 149025 41, 19 141987 41, 24 140709 41, 28 137156 41, 31 133151 41, 36 132366 41, 39 131015 41, 40 129444 41, 43 127832 41, 48 127558 41, 51 127352 41, 55 124291 43, 0 227423 43, 5 186931 43, 8 164655 43, 12 154484 43, 17 146633 43, 20 149369 43, 21 135209 43, 32 136599 43, 33 132766 43, 36 131907 43, 41 130568 43, 45 129271 43, 48 126837 43, 53 128413 43, 56 126023 43, 57 124465 47, 0 253298 47, 4 179848 47, 9 164433 47, 12 164754 47, 13 141709 47, 24 140254 47, 25 142075 47, 28 136060 47, 33 133186 47, 37 131356 47, 40 130229 47, 45 128611 47, 48 129974 47, 49 128627 47, 52 126658 47, 57 125409 49, 0 172969 49, 11 164550 49, 12 155083 49, 15 146835 49, 20 142438 49, 24 139964 49, 27 135421 49, 32 136831 49, 35 133562 49, 36 133513 49, 39 130804 49, 44 128323 49, 47 128327 49, 51 129216 49, 56 126786 49, 59 124463 53, 0 299890 53, 3 210430 53, 7 164093 53, 12 155577 53, 15 153104 53, 16 138588 53, 27 141400 53, 28 137160 53, 31 132066 53, 36 130536 53, 40 130139 53, 43 128610 53, 48 128278 53, 51 128292 53, 52 127327 53, 55 122965 59, 0 675875 59, 1 252003 59, 4 177669 59, 9 162664 59, 12 152139 59, 16 147343 59, 21 140604 59, 24 138113 59, 25 131331 59, 36 131079 59, 37 129197 59, 40 128720 59, 45 128300 59, 49 126447 59, 52 125405 59, 57 As before, this does not include the largest factors of fully-factored Mersenne numbers, since these are not provided by the PrimeNet data, however only a vanishingly small fraction of Mersenne numbers are fully factored. For each value of p mod 60, there are exactly 16 out of 60 valid values for k mod 60. Earlier, we saw that for each value of p mod 12, there were exactly 4 out of 12 possible value for k mod 12. Also, for each value of p mod 4, there were exactly 2 out of 4 possible values for k mod 4. So by increasing the modulus from 4 to 12 to 60, we reduced the number of cases to test from 50% to 33.33% to 26.67%. It seems that the non-uniformity is actually growing as the modulus gets larger. For instance if you are testing a p that has p ≡ 59 (mod 60), then by testing only for k ≡ 1 (mod 60) you will spend one-sixteenth of the time to find nearly one quarter of the potential factors... Maybe I'll look at 420 ( = 2 * (2 * 3 * 5 * 7) ) and 4620 ( = 2 * (2 * 3 * 5 * 7 * 11) ) next, but those would generate huge output files...
2016-05-18, 00:56   #93
GP2

Sep 2003

1010000110012 Posts

Quote:
 Originally Posted by bloodIce It seems that k ≡ 0 (mod 4) is under-represented and k ≡ 1 (mod 4) is over-represented (no matter in which range). The question is why?
Well, it is known that if p ≡ 3 (mod 4) and if 2p+1 is a prime (i.e., p is a Sophie Germain prime), then 2p+1 WILL be a factor of Mp. So in this situation, it's not just k ≡ 1 (mod 4) but k actually = 1. That might explain a bit of the increased frequency of k ≡ 1 (mod 4) but it's surely not the whole picture, and doesn't say anything about the situation for p ≡ 1 (mod 4).

Last fiddled with by GP2 on 2016-05-18 at 00:57

2016-05-18, 02:02   #94
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×641 Posts

You just don't see the sum of them, perhaps.
Quote:
 Originally Posted by LaurV ...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.
Quote:
 Originally Posted by bloodIce ...all exponents are "combed" to TF64, but of course some are factored to higher levels.
Hint: ...and [B]some [/B](that is those where k=1) are factored to [B]much lower[/B] levels, i.e. just this single factor f=2p+1 and then never looked at again. More precisely, [I]some [/I]of them were looked at when someone looked for Mp with most known factors, but not all, -- they were clearly cherry-picked.

Hint 2: if one class is over-represented (1 mod 4 with >25%), then some other(s) should be [B]under[/B]-represented because %-ages add to 100%

Hint 3: (a guess, more or less) if all Mp were uniformly factored to a certain limit and[B] all[/B] factors reported, then the 50-25-25 ratio would have become more even but some noise would have remained. Plus there could be a skew of a more subtle nature, like that recent [URL="http://mersenneforum.org/showthread.php?t=21100"]famous skew[/URL].

 2016-05-18, 03:34 #95 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24×613 Posts Sure. I was thinking exactly to that (all tree "hints"), but no time to post (there was a night here). When k is 0 mod 4, the smallest factor can be 8p+1; when it is 1 mod 4, it can be 2p+1, and when it is 3 mod 4, it can be 6p+1. As we find the factors "in order", and always stop at the smaller we find, this makes the difference. This also propagates up. In fact, all Mp can have 8kp+1 factors (for some k>=1), those are "positive side", i.e. factors which are 1 mod 8. But for p=1 mod 4, their "negative side", i.e. factors of the form -1 mod p, will be of the form 8kp+6p+1, and if p=3 mod 4, they would be 8kp+2p+1 for some k (from zero!). This adds up. Also, don't forget that if p is 3 mod 4 and q=2p+1 is prime, then q divides Mp (that is an old theorem from Sophie Germain). If we would make the same statistics only with factors higher than 8p+1, then the numbers would be more balanced. They would be more balanced if we would have all mersenne numbers completely factored too I said "all 3 hints", because indeed it may be an unbalance caused by more "subtle" forces, like the modularity of mersenne numbers - they are all 3 mod 4, it means that their number of factors which are 1 mod 4 is even, and their number of factors which are 3 mod 4 is odd. Because when you multiply 3*3=9=1 mod 4, so they can't have an even number of factors being 3 mod 4. So, we have 0, 2, 4, 6 etc factors which are 1 mod 4, but we can only have 1, 3, 5, 7 etc factors which are 3 mod 4. That is, if Mp is composite, it must have at least one factor which is 3 mod 4. This could add up to some differences that we see in the 1 and 3 mod 4 versus 0 mod 4 for the k's, but the question is if it worth hunting for it (by changing the class order of mfaktX, or else). My feeling is that is not worth. They always have at least 1 factor which is 3 mod 4, i.e. that is, on the "negative side" (i.e. it is -1 mod 8). And 2p+1 or 6p+1 is heavy here, because we store smallest factors with a higher probability. Note that these are eliminated very fast, it doesn't need to change the class order of mfaktX to get rid of them. Last fiddled with by LaurV on 2016-05-18 at 03:43
2016-05-18, 05:56   #96
bloodIce

Feb 2010
Sweden

17310 Posts

Quote:
 Originally Posted by Batalov Hint: ...and [B]some [/B](that is those where k=1) are factored to [B]much lower[/B] levels, i.e. just this single factor f=2p+1 and then never looked at again. More precisely, [I]some [/I]of them were looked at when someone looked for Mp with most known factors, but not all, -- they were clearly cherry-picked.
Not in the range I pointed. I know it was pointless, but in the range 900M-906M I tried all exponents to TF64 regardless if they have a lower factor or not. Not to mention that all exponents in the whole <1B range are factored to TF60 as result of TJAOI work. Intentionally, I pointed higher range (900M) so there is very little possibility for cherry-picking. There are some cases of course, but there are no Pm1 and ECM, just over-TFed exponents.

2016-05-18, 06:08   #97
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×613 Posts

Quote:
 Originally Posted by LaurV "negative side", i.e. factors of the form -1 mod p,
errata: this should read "-1 mod 8"

2016-05-18, 10:44   #98
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by LaurV errata: this should read "-1 mod 8"
technically so is the even number of 4x+1 factors because then don't add anything to change the 3 mod 4 part of things in theory they can have any number of these factors as long as the multiplication together doesn't exceed the mersenne.

2016-05-18, 21:16   #99
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5EE16 Posts

Quote:
 Originally Posted by LaurV When k is 0 mod 4, the smallest factor can be 8p+1; when it is 1 mod 4, it can be 2p+1, and when it is 3 mod 4, it can be 6p+1. As we find the factors "in order", and always stop at the smaller we find, this makes the difference. This also propagates up.
No! There is an ongoing effort to find all small prime factors for the smallish exponents (so say we surely know all q<2^52 factors for all Mp, where p<10^7 or so). So at least in the first stat there should be no such effect what you write.

I think most of these differences comes from the very small k values, say seeing only k<=100.
q1=6*p+1 is prime with roughly two times higher probability than q2=8*p+1 (you can generalize this),
and use also that for k=1 or 3 mod 4 if q=2*k*p+1 is prime then this divides 2^p-1 with 1/(2*k) probability, for k=0 mod 4 with 1/k probability.
(obviously these are only heuristics). I've gotten even that k=1 mod 4 gives more "small" factors than k=3 mod 4.

To see a real data: trying only p<10^7 and k<=100:
Code:
v=[0,0,0,0];forprime(p=2,10^7,for(k=1,100,q=2*k*p+1;if(Mod(2,q)^p==1&&isprime(q),v[(k%4)+1]++)));v
this results: [58924, 58516, 0, 43331]
using the known data: w=[336365,196835,0,181578];
w-v=[277441, 138319, 0, 138247]
what is very close to the expected 2:1:1 distribution for the possible residues.

 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 16:04.

Tue Nov 30 16:04:20 UTC 2021 up 130 days, 10:33, 0 users, load averages: 1.85, 1.77, 1.57