20120830, 16:32  #12  
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
Quote:
I can get what k*p is mod 120 from them, regardless of p but once p gets involved could it not figure it out ? Edit:maybe it's because too many values can be prime mod 120. Last fiddled with by science_man_88 on 20120830 at 17:20 

20120830, 19:08  #13 
Dec 2011
11·13 Posts 
I think much of this thread is beyond the scope of James' question. I think the last 2 lines of my previous post and the first 5 lines of LaurV's post get to heart of James' question.
A lot of this thread is more about efficiency in hunting for factors than "plausibility". It isn't necessary to try candidates q=2kp+1 that are not prime, because if they are composite, their component factors are probably already known. 256999 (k=4431) is composite and is a factor of M(29). But we probably already knew that 233 (k=4) and 1103 (k=19) were factors of M(29). Most tf algorithms try to ensure q doesn't have any small prime factors before they undertake the divisibility test of M(p)/q. @James: If you seek more than basic "plausibility", then I suggest you apply my plausibility test and *also* compute q=2kp+1. Then, depending on your application you can test q for primality (or probably primality) or you can trial factor q to some level of your choice. Are you "hunting" or "validating" values of k? Last fiddled with by rcv on 20120830 at 19:21 
20120830, 19:11  #14 
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}×19×23 Posts 

20120830, 19:43  #15 
Feb 2010
Sweden
173 Posts 
I wonder if there is only one factor in a class. Is there any way to check if there is one and only factor in each class. If that is true, then 1 class fells off, when a factor is found. If there are 8 or 9 known factors (such exponents are rear on this stage of the project), that will be additional ~1% filtering.

20120830, 22:46  #16 
"Oliver"
Mar 2005
Germany
10001011001_{2} Posts 
Yes, it is possible. Those classes are artificial and are not directly related to mersenne numbers. They help to eleminate composite factor candidates (sieving) from the list more effecient.
You can freely choose the number of classes, but some numbers are "better" than others, e.g. with 4620 those classes remove all composite factor candidates which are a multiple of 3, 5, 7 or 11 and don't satisfy the q == 1 or 7 mod 8 rule. 960 classes survive (20.78%). If you choose 4621 classes than 4620 classes survive (99.98%) because you can only eliminate factor candidates which are a multiple of 4621. Oliver 
20120831, 00:53  #17 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
I realize now basically all I was saying is: > k= and with properties of q and p we should be able to find properties of k. including modular properties.

20120831, 13:26  #18  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
where <modulus> is the modulus used in the first section. and the modulus is used on 2*p in both sections. Last fiddled with by science_man_88 on 20120831 at 13:27 

20121121, 15:36  #19 
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}·19·23 Posts 
Going back to this thread after some time, I've been playing with my PARI code and trying to incorporate some of the ideas presented here, but I'm unable to get it to run any faster than what I was originally using, which is just a "dumb" filter of skipping all k%4==2:
Code:
for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==2,k++); q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;); k++;)); ## = 31.913s Code:
for(i=1, 1000, p=4294949947; k=10000; while(k<20000, while(k%4!=0 && k%4!=1,k++); q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;); k++;)); ## = 31.877s for(i=1, 1000, p=4294949947; k=10000; while(k<20000, q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;); k++;)); ## = 32.168s // on the assumption that 4294949947 % 4 == 3 for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==0k%4==1,,k++); q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;); k++;)); ## = 32.663s for(i=1, 1000, p=4294949947; k=10000; while(k<20000, 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),,k++); q=2*k*p+1; if(lift(Mod(2,q)^p)==1, print("M"p" has a factor: "q); break;); k++;)); ## = 42.424s for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(lift(Mod(2,2*k*p+1)^p) == 1, print("M"p" has a factor: "q); break;); k++;)); ## = 52.559s LaurV's nice description of primorial class filtering was unfortunately beyond my ability to translate into code. 
20121121, 19:04  #20  
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
Quote:
I think I have a few ideas though I ran both codes in version 2.5.1 of Pari: Code:
? for(i=1, 1000, p=4294949947; k=10000; while(k<20000, while(k%4!=0 && k%4!=1,k++); q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;); k++;)); ? ## *** last result computed in 25,264 ms. ? p=4294949947;for(i=1,1000,forstep(k=10000,19999,[1,3],q=2*k*p+1;if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q)))) ? ## *** last result computed in 21,501 ms. 

20121121, 19:12  #21  
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}·19·23 Posts 
Quote:
However your forstep change did provide a 10% performance improvement, so that's a good start. 

20121121, 19:24  #22  
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
Quote:
Last fiddled with by science_man_88 on 20121121 at 19:25 

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 