mersenneforum.org Sophie-Germain sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2014-01-08, 19:11 #1 firejuggler     "Vincent" Apr 2010 Over the rainbow 288410 Posts Sophie-Germain 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 3-PRP! (0.0164s+0.0000s) 2*50000015*2^6277+3 is 3-PRP! (0.0166s+0.0007s) 50000091*2^6208+1 is 3-PRP! (0.0159s+0.0006s) 2*50000091*2^6208+3 is composite: RES64: [99DB9963CADC02CB] (0.0502s+0.0006s) 50000135*2^6287+1 is 3-PRP! (0.0161s+0.0001s) 2*50000135*2^6287+3 is composite: RES64: [FCAA64210051C2F4] (0.0164s+0.0007s) 50000163*2^6200+1 is 3-PRP! (0.0160s+0.0001s) 2*50000163*2^6200+3 is composite: RES64: [8D56C728E7EFFC3F] (0.0476s+0.0006s) 50000167*2^6270+1 is 3-PRP! (0.0163s+0.0001s) 2*50000167*2^6270+3 is composite: RES64: [A418C1326AE85D01] (0.0163s+0.0007s) 50000187*2^6283+1 is 3-PRP! (0.0166s+0.0001s) 2*50000187*2^6283+3 is composite: RES64: [045B1F70DECC6B45] (0.0480s+0.0005s) 50000229*2^6230+1 is 3-PRP! (0.0160s+0.0001s) 2*50000229*2^6230+3 is composite: RES64: [B2A6EB7E8322FD6E] (0.0479s+0.0006s) 50000251*2^6284+1 is 3-PRP! (0.0163s+0.0001s) 2*50000251*2^6284+3 is composite: RES64: [9A56C78E1776A515] (0.0163s+0.0006s) 50000259*2^6281+1 is 3-PRP! (0.0164s+0.0001s) 2*50000259*2^6281+3 is composite: RES64: [A67C2FC9A89CE30B] (0.0478s+0.0008s) 50000265*2^6297+1 is 3-PRP! (0.0162s+0.0001s) 2*50000265*2^6297+3 is composite: RES64: [87C048E4FFAEB5E3] (0.0483s+0.0005s) 50000317*2^6272+1 is 3-PRP! (0.0164s+0.0001s) 2*50000317*2^6272+3 is composite: RES64: [DF2A75D16604E7A9] (0.0164s+0.0006s) 50000325*2^6236+1 is 3-PRP! (0.0160s+0.0001s) 2*50000325*2^6236+3 is composite: RES64: [D747A2F35C2BDD4F] (0.0498s+0.0007s) 50000429*2^6171+1 is 3-PRP! (0.0170s+0.0001s) 2*50000429*2^6171+3 is composite: RES64: [22019FE0A0057A3F] (0.0167s+0.0006s) 50000443*2^6210+1 is 3-PRP! (0.0166s+0.0001s) 2*50000443*2^6210+3 is composite: RES64: [47B1488C097FC7C2] (0.0161s+0.0011s) 50000495*2^6241+1 is 3-PRP! (0.0161s+0.0001s) 2*50000495*2^6241+3 is composite: RES64: [37E0A97E82814D45] (0.0163s+0.0006s) 50000503*2^6286+1 is 3-PRP! (0.0162s+0.0001s) 2*50000503*2^6286+3 is composite: RES64: [4BA8D20C6F34F488] (0.0163s+0.0007s) lresult ouput 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. and yes I found some hit. 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. As for the reason of this... for fun, what else? Last fiddled with by firejuggler on 2014-01-08 at 19:12
 2014-01-09, 07:36 #2 Citrix     Jun 2003 110010001012 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 (10k-1.2M). Last fiddled with by Citrix on 2014-01-09 at 07:39
 2014-01-09, 14:14 #3 firejuggler     "Vincent" Apr 2010 Over the rainbow B4416 Posts Thanks a lot Citrix.
 2014-01-09, 23:28 #4 Ken_g6     Jan 2005 Caught in a sieve 18B16 Posts That's an unusual range. Most people do k*2^n-1 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 CPU-limited), and then you could combine the results somehow. Last fiddled with by Ken_g6 on 2014-01-09 at 23:30
 2014-01-10, 00:09 #5 firejuggler     "Vincent" Apr 2010 Over the rainbow 22×7×103 Posts The fact is, I'm looking for fermat divisors, and the range (k=50e6 to 100e6 and N between 6150-6300) 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trejack Twin Prime Search 10 2016-06-23 15:10 ProximaCentauri Miscellaneous Math 15 2014-12-25 14:26 binu Factoring 3 2013-04-13 16:32 MooooMoo Twin Prime Search 8 2008-11-05 15:03 axn Twin Prime Search 3 2007-01-15 12:57

All times are UTC. The time now is 05:39.

Wed Feb 1 05:39:54 UTC 2023 up 167 days, 3:08, 0 users, load averages: 0.96, 0.89, 0.99