20120829, 23:38  #1  
"James Heinrich"
May 2004
exNorthern Ontario
6401_{8} Posts 
Possible values for k (in Mersenne factors)
I'm trying to figure out the pattern behind what values of k are acceptable for Mersenne factors in the form 2kp+1.
The mersenne.org math page simply says: Quote:
Running through a list of known factors shows that certain values of k just aren't viable, but the pattern is not obvious to me. For example, the first 100 possible values of k are (with blank lines left indicating impossible values): Code:
1 3 4 5 7 8 9 11 12 13 15 16 17 19 20 21 23 24 25 27 28 29 31 32 33 35 36 37 39 40 41 43 44 45 47 48 49 51 52 53 55 56 57 59 60 61 63 64 65 67 68 69 71 72 73 75 76 77 79 80 81 83 84 85 87 88 89 91 92 93 95 96 97 99 100 101 103 104 105 107 108 109 111 112 113 115 116 117 119 120 121 123 124 125 127 128 129 131 132
What are the rules governing which values of k are acceptable? edit: Actually, looking again at the list I now see the obvious tripletgrouping: every 4th number is skipped. Is that it? Last fiddled with by James Heinrich on 20120829 at 23:38 

20120829, 23:53  #2 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
since primes>3 are 1 or 5 mod 6 we can reduce to:
2*k*p+1 = 1 or 5 mod 6 plug in p=p mod 6 and solve for k they will fall in certain classes same with moduli like 120. you can find out things from these. Last fiddled with by ewmayer on 20120830 at 00:16 Reason: remove unnecessary quote of OP 
20120830, 00:26  #3  
"James Heinrich"
May 2004
exNorthern Ontario
3,329 Posts 
Quote:
Please use very simple words in explaining this to me (yes, I know I don't belong in the math forum). So far (k % 4) != 2 seems to hold up against my list of known k values, but I'm not sure if this simple observation is sufficient to determine what k values are acceptable? Quote:


20120830, 00:37  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
example: p=1 mod 6 2*k*p+1 since p=p mod 6 will work we get 2*k*1+1 = 2*k+1 = either 1 or 5 mod 6, k=2 gives you 5 mod 6 and so will increasing k by 3 since 2*3 = 6 so k=2 mod 3 for p=1 mod 6 and 2*k*p+1 = 5 mod 6, what if 2*k*p+1 is 1 mod 6 and p = 1 mod 6 once again 2*k*1+1 = 2*k+1 okay so k=0 works , once again repeating every 3 so k=0 mod 3 so for p= 1 mod 6, k=0 or 2 mod 3 . Last fiddled with by science_man_88 on 20120830 at 00:38 

20120830, 01:29  #5 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
what these have to do with k values in 2*k*p+1 is that these are the values mod 120 that fit being able to be prime and 1 or 7 mod 8, which are the values mod 120, 2*k*p+1 must take on. as shown with mod 6 this can be backtracked to possible k mod 120 values.

20120830, 02:05  #6 
"James Heinrich"
May 2004
exNorthern Ontario
3,329 Posts 
Perhaps I can understand code better than words.
If I understand you correctly, whether or not a certain k is viable depends on p? Can you show me some example code (C, PARI, PHP, pseudo, whatever) that will determine if k is appropriate for any give p? Taking a specific example, how would I determine which values of k<50 are valid for M39183121 (chosen at random but with known factors for k=3,8,48): Code:
p=39183121; for(k=1, 50, if(<something to determine if k is viable>, print(k));); 
20120830, 02:23  #7 
Dec 2011
8F_{16} Posts 
James:
The following are from the comments in my gpusieve.cu code, which is released under GPL, and which is in a BDot source archive, somewhere. The last two lines cut to the chase. The first couple of dozen lines explain "why". Code:
// Furthermore, all candidates must be equal to 1 or 7, // modulo 8 to be a factor of a Mersenne number. This lets // us reduce by another factor of 2 the work we might // otherwise have performed. [It might appear we should be // reducing the work by a factor of 4, but we are inherently // only considering odd candidates, so we can only // eliminate candidates that are equal to 3 or 5, modulo 8.] // // By theorem, all factors of a mersenne number are of the // form, 2*k*p+1, where k is a positive integer and p is the // exponent of the Mersenne number. // // The following table contains (2*k*p) mod 8 for each // possible combination of a kvalue with an odd Mersenne exponent. // // (2*k) mod 8 // p mod 8 0  2  4  6  //  // 1  0  2  4  6  // 3  0  6  4  2  // 5  0  2  4  6  // 7  0  6  4  2  // // Next, we look at the candidates (2*k*p+1) mod 8. The valid // candidates are equal to 1 or 7. Others need not be generated. // // (2*k) mod 8 // p mod 8 0 1 2 3 4 5 6 7 //  // 1  1      7  // 3  1  7      // 5  1      7  // 7  1  7      // // This shows us that if (p mod 4) == 1, then k must equal 0 or 3 (modulo 4). // and if (p mod 4) == 3, then k must equal 0 or 1 (modulo 4). 
20120830, 02:31  #8  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Code:
? p=39183121; for(k=1, 50, if((2*k*p+1)%6==1  (2*k*p+1)%6==5, print(k","k%3));); 2,2 3,0 5,2 6,0 8,2 9,0 11,2 12,0 14,2 15,0 17,2 18,0 20,2 21,0 23,2 24,0 26,2 27,0 29,2 30,0 32,2 33,0 35,2 36,0 38,2 39,0 41,2 42,0 44,2 45,0 47,2 48,0 50,2 moving on they can only work if 2*k*p+1 is 1 or 7 mod 8: Code:
? p=39183121; for(k=1, 50, if(((2*k*p+1)%6==1  (2*k*p+1)%6==5) && ((2*k*p+1)%8==1  (2*k*p+1)%8==7), print(k));); 3 8 11 12 15 20 23 24 27 32 35 36 39 44 47 48 

20120830, 05:32  #9 
Romulan Interpreter
Jun 2011
Thailand
11×853 Posts 
As an addition to what was said, this is exactly what mfakt* is doing with those classes.
(1.) If a factor is 2*k*p+1 AND 8*x+1, then you solve the system in integers and get that the factor is in fact 8*h*p+1, for any h. That is, k=4h, i.e. k=0 (mod 4). (2.) If a factor is 2*k*p+1 AND 8*x1, then you solve the system in integers, but this time you get two solutions, dependent on p: (2.a.) For p=4*t+3, (i.e. p=3 mod 4) the factor is 8*h*p+2*p+1. That is, k=(4*h+1), i.e. k=1 (mod 4). (2.b.) For p=4*t+1, (i.e. p=1 mod 4) the factor is 8*h*p+6*p+1. That is, k=(4h+3), i.e. k=3 (mod 4). This automatically eliminates all the candidates which are 3 or 5 (mod 8). Only this in itself would be enough to filter the values of k quite a lot. For example, as your 39183121 is 1 (mod 4), it can have only factors of the form (1) and (2b). This already filters the values of k to a half, like 3, 4, 7, 8, 11, 12, 15, 16, etc. Adding to this the fact that the factors are prime: we can consider the first primorial, 6, and say the factors must be 1 or 5 mod 6, you already make a lot of progress, about another quarter of the remaining candidates are gone. In fact, 12 would be a better choice then 6, because is divisible by 4, and remember, k has a nice modularity with 4. It is essential that the modulus be multiple of 4. Anyhow you will reach this after calculus, if you want to eliminate the candidates which are 3 or 5 mod 8. If you take 12, a candidate can be prime only if it is 1, 5, 7, 11 (mod 12), but the 5 and 11 (mod 12) may be (or may be not, depending on p) 5 or 3 mod 8, so they are not wanted from the start. For different p, other two classes may not be wanted, but two classes will ALWAYS be eliminated from the start. In fact, 6 has nothing magic in it, it is just the first primorial. A much better way is to consider a larger primorial, multiplied by two, for example 2*(2*3*5*7*11). If you compute this, it is 4620, and now you get to mfakt* and to where the number of classes come from. As Oliver explained so many times, those are modularity classes for k in expression q=2*k*p+1. For this expression to be prime, to be 1 or 7 (mod 8) the classes of k are highly dependent of the classes of p. For example, for the chosen number p=39183121, which is 1 (mod 4) and 901 (mod 4620):  k can not be 1 (mod 4620). In this case q will be 2*901+1=1803 (mod 4620) which is not prime (divisible by 3). And so on for the classes of modularity 1, 4, 7, 10, +3 +3 etc). This eliminates a third of the classes.  k can not be 2 (mod 4620)  this is divisible by 5. And same for classes 2, 7, 12, 17, +5, +5 ...  etc. This is much like the Eratosthenes' sieve, but applied to 4620 numbers only. Once you get this class is divisible by 3, all +3 are divisible by 3. If this class is divisible by 11, all +11 classes are divisible by 11. [edit: also, if a for a k we have 2*k*p+1 is 3 or 5 (mod 8), then 2*(k+4620)*p+1 will also be 3 or 5 (mod 8), so once you eliminated a class, you don't need to care about it during sieving process, whole class is safely eliminated, there will be no 3 or 5 (mod 8) numbers in the sieve  see below] At the end, a lot of classes are eliminated because they can't result in prime numbers. The 3 or 5 mod 8 are eliminated "by construction". All this process takes a blink of an eye and if you start mfactc on this number you will see that it starts testing only the classes 0, 3, 8, 11, 15, 20, 24, 35, 36, etc, only the classes which are blue in the attached table. Only 960 classes survive the "filtering". It does not seem to be very regulated, but the process itself is a very deterministic :D For example in class 3 there will be k of the form: 3, 3+4620, 3+2*4620, 3+3*4620, ..... etc, resulting in corespondent factorcandidates of the form 2*3*39183121+1, 2*(3+4620)*39183121+1, 2*(3+2*4620)*39183121+1, 2*(3+3*4620)*39183121+1, 2*(3+4*4620)*39183121+1, ... etc. The candidates of the form 2*(k+n*4620)*p+1, with all k in the 960 remaining classes and natural n, are the only candidates having the chance to be prime, and to be 1 or 7 mod 8. Other numbers with k in different classes CANNOT be factors of Mp (they are either not prime, or not 1,7 mod 8). More then this you can't dig. Further on, the candidates in each class have to be sieved with small primes (done by CPU) and only the surviving will be used for modular exponentiation to test if 2^39183121=1 mod each survivor (done by GPU). That is one of the reasons why mfaktc is so efficient. Last fiddled with by LaurV on 20120830 at 06:23 
20120830, 06:38  #10 
Romulan Interpreter
Jun 2011
Thailand
24A7_{16} Posts 
[time limit still editing it every 5 minutes :D. Now I am trying to change the ending, as I did some calculus meantime:]
[discussion was related to class k=3, modified example to n=10] resulting in corespondent factorcandidates of the form 2*3*39183121+1 = 235098727 2*(3+4620)*39183121+1 = 362287136767 2*(3+2*4620)*39183121+1 = 724339174807 2*(3+3*4620)*39183121+1 = 1086391212847 2*(3+4*4620)*39183121+1 = 1448443250887 2*(3+5*4620)*39183121+1 = 1810495288927 2*(3+6*4620)*39183121+1 = 2172547326967 2*(3+7*4620)*39183121+1 = 2534599365007 2*(3+8*4620)*39183121+1 = 2896651403047 2*(3+9*4620)*39183121+1 = 3258703441087 2*(3+10*4620)*39183121+1 = 3620755479127 ... etc. <snip see the post above > In the example above, sieving the class k=3 with primes up to 10000 will eliminate all the candidates, except for n=0,3,6,8. Remark that only candidates for n=0,6 are prime (marked in bold), but we don't know this, and deciding their primality is more costly then doing exponentiation. Last fiddled with by LaurV on 20120830 at 06:54 Reason: 10k>10000 (eliminate confusion) 
20120830, 15:07  #11 
Einyen
Dec 2003
Denmark
3,079 Posts 
If you look at a specific exponent p then there is lots of k values which cannot result in a mersenne factor q=2kp+1.
But if you look at a specific k value and ask if there is any mersenne number 2^{p}1 which has the factor q=2kp+1 then the only kvalues that does not correspond to a factor is those with k=2 (mod 4). This comes from q has to be 1 or 7 (mod 8). Prime p>2 is equal to 1,3,5,7 (mod 8), so 2*p is 2 or 6 (mod 8), and for k=2,6 (mod 8): 2kp+1 is always 5 (mod 8). Looking at the 16 possible values for q (mod 120) does not give any further restriction on k. 
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 