20140108, 19:11  #1 
Apr 2010
Over the rainbow
9B3_{16} Posts 
SophieGermain sieve
I'm looking for a SG siever, as Newpgen can only sieve for one n at a time. More particulary, for the k*2^n+1 & k*2^(n+1)+3.
Right now, i'm looking for Fermat divisor with k between 50e6 and 100e6 with N between 6150 and 6300. The best method I found so far is to take the prime found with PFGW , convert to newpgen format, add the SG header (1:P:0:2:4097) then pass the file to LLR (PFGW doesn't seem to handle it well) pfgw output Code:
50000015*2^6277+1 is 3PRP! (0.0164s+0.0000s) 2*50000015*2^6277+3 is 3PRP! (0.0166s+0.0007s) 50000091*2^6208+1 is 3PRP! (0.0159s+0.0006s) 2*50000091*2^6208+3 is composite: RES64: [99DB9963CADC02CB] (0.0502s+0.0006s) 50000135*2^6287+1 is 3PRP! (0.0161s+0.0001s) 2*50000135*2^6287+3 is composite: RES64: [FCAA64210051C2F4] (0.0164s+0.0007s) 50000163*2^6200+1 is 3PRP! (0.0160s+0.0001s) 2*50000163*2^6200+3 is composite: RES64: [8D56C728E7EFFC3F] (0.0476s+0.0006s) 50000167*2^6270+1 is 3PRP! (0.0163s+0.0001s) 2*50000167*2^6270+3 is composite: RES64: [A418C1326AE85D01] (0.0163s+0.0007s) 50000187*2^6283+1 is 3PRP! (0.0166s+0.0001s) 2*50000187*2^6283+3 is composite: RES64: [045B1F70DECC6B45] (0.0480s+0.0005s) 50000229*2^6230+1 is 3PRP! (0.0160s+0.0001s) 2*50000229*2^6230+3 is composite: RES64: [B2A6EB7E8322FD6E] (0.0479s+0.0006s) 50000251*2^6284+1 is 3PRP! (0.0163s+0.0001s) 2*50000251*2^6284+3 is composite: RES64: [9A56C78E1776A515] (0.0163s+0.0006s) 50000259*2^6281+1 is 3PRP! (0.0164s+0.0001s) 2*50000259*2^6281+3 is composite: RES64: [A67C2FC9A89CE30B] (0.0478s+0.0008s) 50000265*2^6297+1 is 3PRP! (0.0162s+0.0001s) 2*50000265*2^6297+3 is composite: RES64: [87C048E4FFAEB5E3] (0.0483s+0.0005s) 50000317*2^6272+1 is 3PRP! (0.0164s+0.0001s) 2*50000317*2^6272+3 is composite: RES64: [DF2A75D16604E7A9] (0.0164s+0.0006s) 50000325*2^6236+1 is 3PRP! (0.0160s+0.0001s) 2*50000325*2^6236+3 is composite: RES64: [D747A2F35C2BDD4F] (0.0498s+0.0007s) 50000429*2^6171+1 is 3PRP! (0.0170s+0.0001s) 2*50000429*2^6171+3 is composite: RES64: [22019FE0A0057A3F] (0.0167s+0.0006s) 50000443*2^6210+1 is 3PRP! (0.0166s+0.0001s) 2*50000443*2^6210+3 is composite: RES64: [47B1488C097FC7C2] (0.0161s+0.0011s) 50000495*2^6241+1 is 3PRP! (0.0161s+0.0001s) 2*50000495*2^6241+3 is composite: RES64: [37E0A97E82814D45] (0.0163s+0.0006s) 50000503*2^6286+1 is 3PRP! (0.0162s+0.0001s) 2*50000503*2^6286+3 is composite: RES64: [4BA8D20C6F34F488] (0.0163s+0.0007s) Code:
50000015*2^6277+1 is prime! Time : 42.616 ms. 100000030*2^6277+3 is not prime. RES64: 23B1D99649043283 Time : 44.281 ms. 50000091*2^6208+1 is prime! Time : 43.337 ms. 100000182*2^6208+3 is not prime. RES64: 99DB9963CADC02CB Time : 73.486 ms. 50000135*2^6287+1 is prime! Time : 49.604 ms. 100000270*2^6287+3 is not prime. RES64: FCAA64210051C2F4 Time : 42.066 ms. 50000163*2^6200+1 is prime! Time : 42.613 ms. 100000326*2^6200+3 is not prime. RES64: 8D56C728E7EFFC3F Time : 72.979 ms. 50000167*2^6270+1 is prime! Time : 38.726 ms. 100000334*2^6270+3 is not prime. RES64: A418C1326AE85D01 Time : 44.334 ms. 50000187*2^6283+1 is prime! Time : 53.914 ms. 100000374*2^6283+3 is not prime. RES64: 045B1F70DECC6B45 Time : 70.249 ms. 50000229*2^6230+1 is prime! Time : 39.567 ms. 100000458*2^6230+3 is not prime. RES64: B2A6EB7E8322FD6E Time : 71.958 ms. 50000251*2^6284+1 is prime! Time : 48.216 ms. 100000502*2^6284+3 is not prime. RES64: 9A56C78E1776A515 Time : 44.708 ms. 50000259*2^6281+1 is prime! Time : 43.079 ms. 100000518*2^6281+3 is not prime. RES64: A67C2FC9A89CE30B Time : 90.409 ms. 50000265*2^6297+1 is prime! Time : 204.661 ms. 100000530*2^6297+3 is not prime. RES64: 87C048E4FFAEB5E3 Time : 92.486 ms. 50000317*2^6272+1 is prime! Time : 38.953 ms. 100000634*2^6272+3 is not prime. RES64: DF2A75D16604E7A9 Time : 44.580 ms. 50000325*2^6236+1 is prime! Time : 43.489 ms. 100000650*2^6236+3 is not prime. RES64: D747A2F35C2BDD4F Time : 71.081 ms. 50000429*2^6171+1 is prime! Time : 40.058 ms. 100000858*2^6171+3 is not prime. RES64: 22019FE0A0057A3F Time : 44.556 ms. 50000443*2^6210+1 is prime! Time : 35.011 ms. 100000886*2^6210+3 is not prime. RES64: 47B1488C097FC7C2 Time : 36.916 ms. 50000495*2^6241+1 is prime! Time : 68.993 ms. 100000990*2^6241+3 is not prime. RES64: 37E0A97E82814D45 Time : 45.293 ms. 50000503*2^6286+1 is prime! Time : 34.812 ms. 100001006*2^6286+3 is not prime. RES64: 4BA8D20C6F34F488 Time : 36.231 ms. Code:
50063587*2^6290+1 is prime! Time : 48.686 ms. 100127174*2^6290+3 is prime! Time : 53.284 ms. 50138695*2^6216+1 is prime! Time : 94.767 ms. 100277390*2^6216+3 is prime! Time : 102.605 ms. 50232221*2^6235+1 is prime! Time : 44.790 ms. 100464442*2^6235+3 is prime! Time : 47.948 ms. Last fiddled with by firejuggler on 20140108 at 19:12 
20140109, 07:36  #2 
Jun 2003
627_{16} Posts 
http://www.underbakke.com/primes/
might be helpful. I would suggest searching k between 50e6 and 100e6 with N between 6150 and 6300 using the above. (This range might have already been searched before). Then test with PFGW or LLR and then test the primes found for SG candidates. It would be fun to have a coordinated search for Fermat factors for small n (that do not end up on the top 5000 list ie n<250k) and large k ranges (10k1.2M). Last fiddled with by Citrix on 20140109 at 07:39 
20140109, 14:14  #3 
Apr 2010
Over the rainbow
100110110011_{2} Posts 
Thanks a lot Citrix.

20140109, 23:28  #4 
Jan 2005
Caught in a sieve
2·197 Posts 
That's an unusual range. Most people do k*2^n1 for SG, but maybe that's why you picked this range. It doesn't look like David Underbakke's software does k*2^n+3.
My ppsieve won't do the +3s, but it would be really fast on the +1s. You can even run the CUDA or OpenCL version if you have an appropriate graphics card. NewPGen can be set to work on one N up to a given P, and then jump to the next N. Not as efficient as ppsieve, but maybe you could have it sieve the +3s on your CPU while ppsieve does the +1s on a GPU (Edit: and one CPU core  that small range of N's is almost certainly going to be CPUlimited), and then you could combine the results somehow. Last fiddled with by Ken_g6 on 20140109 at 23:30 
20140110, 00:09  #5 
Apr 2010
Over the rainbow
9B3_{16} Posts 
The fact is, I'm looking for fermat divisors, and the range (k=50e6 to 100e6 and N between 61506300) is at the factoring limit as far as W.keller page would say.
I got interested in this because of my searsh for low prime the 12/31, when Proth.exe told me that 31122013*2^56+1 and 31122013*2^57+3 were SG prime. I know of ppsieve, and will use it again soon.ATM I use fermfact. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sophie Germain Twins  Trejack  Twin Prime Search  10  20160623 15:10 
SophieGermain primes as Mersenne exponents  ProximaCentauri  Miscellaneous Math  15  20141225 14:26 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
Sophie Germains, multiple nranges, future of TPS  MooooMoo  Twin Prime Search  8  20081105 15:03 
Left over Sophie Germain primes?  axn  Twin Prime Search  3  20070115 12:57 