mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-08-29, 23:38   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3·1,061 Posts
Default 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:
One very nice property of Mersenne numbers is that any factor q of 2P-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.
This mentions constraints on factor q, but not on k.

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
The only patterns I see (whether real or imagined):
  • all values of 2*<single prime factor> (e.g. 6, 10, 14, 22, 26, 34) are not-acceptable
  • all prime values (except 2) are acceptable.
  • all powers of a single prime (4,8,16,32,64,128; 3,9,27,81) are acceptable
But that doesn't explain 18,30,42,50

What are the rules governing which values of k are acceptable?


edit: Actually, looking again at the list I now see the obvious triplet-grouping: every 4th number is skipped. Is that it?

Last fiddled with by James Heinrich on 2012-08-29 at 23:38
James Heinrich is offline   Reply With Quote
Old 2012-08-29, 23:53   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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 2012-08-30 at 00:16 Reason: remove unnecessary quote of OP
science_man_88 is offline   Reply With Quote
Old 2012-08-30, 00:26   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3×1,061 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
I understood none of what you said, unfortunately.

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:
Originally Posted by science_man_88
this has been discussed before but:

? for(x=1,120,if(gcd(x,120)==1 && (x%8==7 || x%8==1),print1(x",")))
1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119,
I'm also not sure what this has to do with k values?
James Heinrich is offline   Reply With Quote
Old 2012-08-30, 00:37   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I understood none of what you said, unfortunately.

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?

I'm also not sure what this has to do with k values?
the values of k mod a modulus depend on p mod the modulus because given that and the values a prime can take on mod that modulus 2*k*p+1 can be solved down to possible values of k:

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 2012-08-30 at 00:38
science_man_88 is offline   Reply With Quote
Old 2012-08-30, 01:29   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by James Heinrich View Post

I'm also not sure what this has to do with k values?
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.
science_man_88 is offline   Reply With Quote
Old 2012-08-30, 02:05   #6
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3·1,061 Posts
Default

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)););
James Heinrich is offline   Reply With Quote
Old 2012-08-30, 02:23   #7
rcv
 
Dec 2011

11×13 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Perhaps I can understand code better than words.
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 k-value 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).
rcv is offline   Reply With Quote
Old 2012-08-30, 02:31   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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)););
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
I checked if 2*k*p+1 was 1 or 5 mod 6 if so k is a possibility for p in this case, it's shown they are all 0 or 2 mod 3.


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
these k survive when that condition is met we could of figured out when the mod groups crossed mod another number but I left it simple.
science_man_88 is offline   Reply With Quote
Old 2012-08-30, 05:32   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

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*x-1, 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.
Click image for larger version

Name:	mfcls.jpg
Views:	232
Size:	214.6 KB
ID:	8506

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 factor-candidates 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 2012-08-30 at 06:23
LaurV is offline   Reply With Quote
Old 2012-08-30, 06:38   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

[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 factor-candidates 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 2012-08-30 at 06:54 Reason: 10k->10000 (eliminate confusion)
LaurV is offline   Reply With Quote
Old 2012-08-30, 15:07   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·331 Posts
Default

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 2p-1 which has the factor q=2kp+1 then the only k-values 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.
ATH is online now   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 20:37.

Fri Nov 27 20:37:19 UTC 2020 up 78 days, 17:48, 3 users, load averages: 1.49, 1.38, 1.56

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