Go Back > Great Internet Mersenne Prime Search > Software

Thread Tools
Old 2014-01-08, 19:11   #1
firejuggler's Avatar
Apr 2010
Over the rainbow

9B316 Posts
Default 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
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
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.
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
firejuggler is online now   Reply With Quote
Old 2014-01-09, 07:36   #2
Citrix's Avatar
Jun 2003

62716 Posts

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
Citrix is offline   Reply With Quote
Old 2014-01-09, 14:14   #3
firejuggler's Avatar
Apr 2010
Over the rainbow

1001101100112 Posts

Thanks a lot Citrix.
firejuggler is online now   Reply With Quote
Old 2014-01-09, 23:28   #4
Ken_g6's Avatar
Jan 2005
Caught in a sieve

2·197 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
Ken_g6 is offline   Reply With Quote
Old 2014-01-10, 00:09   #5
firejuggler's Avatar
Apr 2010
Over the rainbow

9B316 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.
firejuggler is online now   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Sophie Germain Twins Trejack Twin Prime Search 10 2016-06-23 15:10
Sophie-Germain primes as Mersenne exponents ProximaCentauri Miscellaneous Math 15 2014-12-25 14:26
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
Sophie Germains, multiple n-ranges, future of TPS MooooMoo Twin Prime Search 8 2008-11-05 15:03
Left over Sophie Germain primes? axn Twin Prime Search 3 2007-01-15 12:57

All times are UTC. The time now is 00:25.

Thu Dec 3 00:25:30 UTC 2020 up 83 days, 21:36, 1 user, load averages: 1.28, 1.66, 1.66

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.