Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Sophie Germain Prime Search :
Possible interest in searching n=1.7M and/or n=3.322M once n=1.29M is complete?
Author 
Message 

I've done some quadsieving on n=1.7M and on n=3.322M and was wondering whether anyone here is interested in eventually testing those candidates. Nothing's been set in stone yet, but TPS may soon start testing n=1.7M and/or n=3.322M, either on a PRPNet server or as manual reservations on the TPS site.
However, unless TPS gets exceptionally lucky, there won't be a twin or sophie found for either candidate by the time our n=1.29M file wraps up a few years from now. At that time, if the admins agree, we could then work on the n=1.7M and n=3.322M candidates that haven't yet been searched by TPS. It would also be up to the admins, but another thing that could be considered is reviving the old TPS badge for those candidates.
In case anyone's curious, those two n's were chosen primarily for efficiency, as they were near an FFT length and are just over 500,000 digits and 1,000,000 digits long (more details are available at: https://www.mersenneforum.org/showthread.php?t=28336). As an added bonus, quadsieving yields a greater chance of finding sophies than triplesieving, which was used for n=1.29M (this comparison assumes that you're quadsieving and triplesieving the same nvalue).
Feedback is greatly appreciated, so please let me know your thoughts. Thanks!
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  


Yes, it is a shame that our SGS project (at n=1.29M) is not based on a proper quadsieve.
But how much sieving work does it take to reach a point where it is reasonable to start primality tests of numbers with the new exponent? You say you already sieved for two new n. How deeply? How many candidates survived the sieving?
Personally, I would not mind if PrimeGrid abandoned the current SGS region (n=1.29M) and went to new territory already. But as I understand, the current plan (and promise?) is to stay there until the old sievefile is exhausted.
Of course, a new bigger n should be run with LLR2 with the Gerbicz hardware error check and the Pietrzak fast verification enabled.
/JeppeSN  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13956 ID: 53948 Credit: 393,160,197 RAC: 187,115

Personally, I would not mind if PrimeGrid abandoned the current SGS region (n=1.29M) and went to new territory already. But as I understand, the current plan (and promise?) is to stay there until the old sievefile is exhausted.
Of course, a new bigger n should be run with LLR2 with the Gerbicz hardware error check and the Pietrzak fast verification enabled.
/JeppeSN
Also, there's higher priority projects that need to get done sooner, so even if we wanted to start a new SGS range there would be things ahead of it in the queue.
____________
My lucky number is 75898^{524288}+1  


Yes, it is a shame that our SGS project (at n=1.29M) is not based on a proper quadsieve.
But how much sieving work does it take to reach a point where it is reasonable to start primality tests of numbers with the new exponent? You say you already sieved for two new n. How deeply? How many candidates survived the sieving?
Personally, I would not mind if PrimeGrid abandoned the current SGS region (n=1.29M) and went to new territory already. But as I understand, the current plan (and promise?) is to stay there until the old sievefile is exhausted.
Of course, a new bigger n should be run with LLR2 with the Gerbicz hardware error check and the Pietrzak fast verification enabled.
/JeppeSN
Thanks for your input!
Calculating the ideal sieve depth for triple and quad sieves is a bit tricky since the number of remaining candidates drops much faster than the average number of tests per prime. For example, let's suppose you sieved k=11T for n=3.322M. At a sieve depth of p=10G, you'd expect to find an average of one mega prime for every 56,150 completed tests, and there would be approximately 1,468,000 candidates in the file. If you sieved the same file to p=10T instead, you'd expect to find an average of one mega prime for every 43,192 tests, but there would only be about 514,000 candidates left in the file.
In case anyone's interested, the stats for n=1.7M are below. Note that the number of candidates in the sieve file is the same for both n=1.7M and n=3.322M; it's the number of tests per prime that's different.
p=1G: 2,237,000 candidates per 1T; 31,928 tests per prime
p=10G: 1,468,000 candidates per 1T; 28,735 tests per prime
p=100G: 1,003,000 candidates per 1T; 26,123 tests per prime
p=1T: 708,000 candidates per 1T; 23,946 tests per prime
p=10T: 514,000 candidates per 1T; 22,104 tests per prime
p=100T: 382,000 candidates per 1T; 20,525 tests per prime
p=1P: 290,000 candidates per 1T; 19,157 tests per prime
p=10P: 224,000 candidates per 1T; 17,960 tests per prime
The optimal sieve depth is therefore generally much lower than it would be for a twinonly sieve. IIRC, n=333333 was twinsieved to p=25000T, n=666666 was quadsieved to p=200T, and n=1.29M was triplesieved to p=1500T.
I completely agree with you on promoting quad sieving and doing the faster Gerbicz/Pietrzak verification instead of running two separate LLR tests and hoping that you're the first one to finish. I also ran the calcs and found that even if n=1.29M were quadsieved to only p=3T (!), a random candidate from that file would have a greater chance of being either a twin or a sophie than if it were triplesieved to the actual sieve depth of p=1500T.
AFAIK, the admins have wanted to finish n=1.29M before starting a new n, but if they change their mind, I can provide the file earlier (it's sieved to a few hundred T). But while I'm confident about those nvalues, I think it would still be a good idea to confirm on many different CPUs that n=1.7M and n=3.322M are indeed the best choices (see https://www.primegrid.com/forum_thread.php?id=4284 for reference). If interested crunchers could post their CPU specs and their times on the following k/n values, it'll be a great help.
1651608592:Z:3:2:46
100000000311945 1660000
100000000695105 1680000
100000000418475 1700000
100000000045455 1720000
100000000734975 3282000
100000001333085 3302000
100000000362885 3322000
100000000678245 3342000
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  


If you or someone else posts the right command line arguments to use to get the desired information, I’d be happy to check FFT sizes on the various computers I own.
____________
 

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 803 ID: 164101 Credit: 305,700,039 RAC: 5,444

Calculating the ideal sieve depth for triple and quad sieves...
See Quad Sieve for twin and Sophie Germain primes and the qsieve project.
For one megatwin or megaSG, more than a billion candidates must be tested and more than 35,000 megaprimes are needed.
Then the sieve must be a distributed project. It should run concurrently with the twin/SG search.
I wrote on Discord:
The successor of WW could be a Quad Sieve for the search for twin and SG primes.
The two programs are not so different: (1) a fast prime number generator, (2) the evaluation of a relation modulo p and what's new for qsieve (3) fill a bitmap.
mfl0p already wrote (1) and (2) for WW.
qsieve defines a possible method. It the target is 600,000+ digits, we can start at n_{0} = 2M. Each task checks 3 <= k < 2^{32} and n_{i} <= n < n_{i} + 64. A first task can test p < 10^{13}, then 141k candidates are generated (a small file). With 100 or 1000 tasks per block, the depth of the sieve can be p_{max} = 10^{15} or 10^{16} and the number of remaining candidates is 80k or 60k. We can set k < 2^{32} and the blocks are n in [2M, 2M+64[, [2M+64, 2M+128[, ...
The size of the bitmap is 1 gigabyte. If it was a problem 10 years ago, it is not anymore. The sieve can run on GPU or CPU and be a distributed search.
If someone is interested in, qsieve is a proof of concept but a real program for a distributed search has to be done. And for now, there are other developments I would like to work on.  


If you or someone else posts the right command line arguments to use to get the desired information, I’d be happy to check FFT sizes on the various computers I own.
Thanks for your offer!
Some time ago, Michael Goetz posted a helpful guide at: https://www.primegrid.com/forum_thread.php?id=4284&nowrap=true#53322
[Noob mode on]
What's the command I should give to llr?
[Noob mode off]
Copy the numbers from Lennart's post (including the header line into a file, e.g., "lennart.in") and then use the following command line:
llr d lennart.in
The "d" causes llr to print out information as it crunches.
 break 
Lennart, I just started running that bunch on my Core2Quad Q6600 @2.4GHz. The first one is running at about 2.243 ms per iteration. I'll post the full results once it's done.
Another option would be to use the GUI version of LLR, which is available for download at: http://jpenne.free.fr/index2.html . But if you're still having difficulties, please let us know.
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  


Personally, I would not mind if PrimeGrid abandoned the current SGS region (n=1.29M) and went to new territory already. But as I understand, the current plan (and promise?) is to stay there until the old sievefile is exhausted.
Of course, a new bigger n should be run with LLR2 with the Gerbicz hardware error check and the Pietrzak fast verification enabled.
/JeppeSN
Also, there's higher priority projects that need to get done sooner, so even if we wanted to start a new SGS range there would be things ahead of it in the queue.
Yeah, an=3.322M search would currently compete with PPS and GFN17 since they all have a similar number of digits.
There's plenty of time to decide, but once we're done with n=1.29M, I wonder whether it's better to run both n=1.7M and n=3.322M at the same time, or whether we should continue to do one nvalue at a time (this assumes that the timings for both exponents are confirmed to be good).
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13956 ID: 53948 Credit: 393,160,197 RAC: 187,115

Some time ago, Michael Goetz posted a helpful guide at: https://www.primegrid.com/forum_thread.php?id=4284&nowrap=true#53322
The only important words there are the first three.
____________
My lucky number is 75898^{524288}+1  


Some time ago, Michael Goetz posted a helpful guide at: https://www.primegrid.com/forum_thread.php?id=4284&nowrap=true#53322
The only important words there are the first three.
I just tried it on the latest LLR version (4.0.3), and fortunately, those instructions still seem to work. The process is pretty much the same  first, create a new file called "timings.txt" containing the following:
1651608592:Z:3:2:46
100000000311945 1660000
100000000695105 1680000
100000000418475 1700000
100000000045455 1720000
100000000734975 3282000
100000001333085 3302000
100000000362885 3322000
100000000678245 3342000
Then, put the timings.txt file in the same folder as the LLR folder and use the following command: cllr64 d timings.txt
The test should begin; I've also taken a screenshot in case it helps: https://imgur.com/NotyJtJ
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  


Yes, it is a shame that our SGS project (at n=1.29M) is not based on a proper quadsieve.
But how much sieving work does it take to reach a point where it is reasonable to start primality tests of numbers with the new exponent? You say you already sieved for two new n. How deeply? How many candidates survived the sieving?
Personally, I would not mind if PrimeGrid abandoned the current SGS region (n=1.29M) and went to new territory already. But as I understand, the current plan (and promise?) is to stay there until the old sievefile is exhausted.
AFAIK, the admins have wanted to finish n=1.29M before starting a new n, but if they change their mind, I can provide the file earlier (it's sieved to a few hundred T).
n=1.7M has been sieved to p=540T for k=1750T. It's now available for testing on PRPNet (port 12000) at TPS:
http://www.noprimeleftbehind.net/tps/ .
Number of candidates that survived the testing: 233.6M
Probability of finding at least one significant prime pair (either twin or Sophie Germain) in that range: 84%
Probability of finding at least one Sophie: 71%
Probability of finding at least one twin: 46%
For reference, here were the stats for PrimeGrid's n=666666 quad sieve:
Range: k=141T
Sieve depth: p=200T
Candidates remaining: 34.2M
Probability of one or more significant pair = 80%
Probability of one or more SG = 67%
Probability of one or more Twin = 42%
Note that since PrimeGrid is only doing n=1.29M now, there won't be any PSA or SGS credits awarded for n=1.7M. You get bragging points on TPS, though ;)
On a related note, quadsieving for n=3.322M is currently a bit over p=700T and will be available for testing at TPS in the near future. Happy prime hunting!
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  


See Quad Sieve for twin and Sophie Germain primes and the qsieve project.
For one megatwin or megaSG, more than a billion candidates must be tested and more than 35,000 megaprimes are needed.
Then the sieve must be a distributed project. It should run concurrently with the twin/SG search.
I wrote on Discord:
The successor of WW could be a Quad Sieve for the search for twin and SG primes.
The two programs are not so different: (1) a fast prime number generator, (2) the evaluation of a relation modulo p and what's new for qsieve (3) fill a bitmap.
mfl0p already wrote (1) and (2) for WW.
qsieve defines a possible method. It the target is 600,000+ digits, we can start at n_{0} = 2M. Each task checks 3 <= k < 2^{32} and n_{i} <= n < n_{i} + 64. A first task can test p < 10^{13}, then 141k candidates are generated (a small file). With 100 or 1000 tasks per block, the depth of the sieve can be p_{max} = 10^{15} or 10^{16} and the number of remaining candidates is 80k or 60k. We can set k < 2^{32} and the blocks are n in [2M, 2M+64[, [2M+64, 2M+128[, ...
The size of the bitmap is 1 gigabyte. If it was a problem 10 years ago, it is not anymore. The sieve can run on GPU or CPU and be a distributed search.
If someone is interested in, qsieve is a proof of concept but a real program for a distributed search has to be done. And for now, there are other developments I would like to work on.
I'm excited to announce that n=3.322M has been quadsieved to p=1130T (a bit over 2^50) and is now available for testing on TPS port 13000. Let's see if we can find that megatwin or Sophie before 2033 ;)
____________
My largest prime: 342924651 · 2^33949391 (1,021,988 digits)
My largest twin prime: 12599682117 · 2^211088+/1 (63,554 digits)
My pictures: https://www.flickr.com/people/michaelkwok/  

Post to thread
Message boards :
Sophie Germain Prime Search :
Possible interest in searching n=1.7M and/or n=3.322M once n=1.29M is complete? 