
View Poll Results: Will you help me sieve these 10m digit candidates?  
Yes, definately!  0  0%  
Maybe...  5  41.67%  
No.  5  41.67%  
No, and I'm willing you to die with hate rays.  2  16.67%  
Voters: 12. You may not vote on this poll 

Thread Tools 
20080515, 19:58  #1 
Oct 2007
Manchester, UK
17×79 Posts 
Help Sieving 10 Million Digit Candidates
Hey everyone, apologies if this is the wrong forum but I was wondering how many people would be interested in helping to sieve some 10 million digit candidates?
The candidate range I'm sieving is: k = 27 for 33,219,273 <= n <= 33,554,432 The aim of the project is to make available a relatively large number of candidates that have been sieved very deeply (though not as deeply as GIMPS). Currently there are just under 15,000 candidates remaining, and the sieve is still removing candidates quite frequently. I need help to sieve the candidates to at least 1 quadrillion (~ 2^50), 2 quadrillion would be nice (~ 2^51), and 4 quadrillion would be perfect (~ 2^52). I've been sieving for some time by myself and I'm at 150 trillion now (a bit past 2^47), with other people helping on the forum I hope the sieving could be sped up significantly. I've been sieving on a Core 2 Duo E6600 and an AMD Athlon 3200+. The Athlon XP can sieve 1 trillion in 3 days, and each core of the E6600 can sieve 1 T in 2 days. It would take me another 21 months to get to 1 quadrillion by myself. If you're not convinced yet, here are some facts:

20080515, 22:02  #2  
Jul 2003
wear a mask
2·5·157 Posts 
Quote:
Do you really want to ask people to help you in a project 1) that will require A LOT of computational time and 2) with such a high chance of failure? just food for thought.... 

20080516, 00:20  #3 
Nov 2003
2×1,811 Posts 
There was already a similar project to sieve k=3, 5, and some other small Ks at n=33M aiming at a 10Mdigit prime but I don't know what happened to it. Most likely people lost interest as nobody was willing to dedicate machines to run LLR long enough (meaning 36 months).
Therefore, what's most important for your project IMO is not the sieving depth but willingness to dedicate machines to run LLR. The next most important thing is the selection of k and n. After k=1 (Mersennes) the next "best" K to try is k=3 followed by 5, 7 and so on because they require smaller FFT lengths (meaning faster LLR exe times) than larger Ks. And the range of n has to be large enough so that chances of finding a prime are reasonable. In case of k=27 I'm afraid your range only 340k wide is too small. Why? Because k=27 already has a gap between primes larger than 300k at n=1M. Here is the list of all k=27 primes with more than 100k digits: 340682, 444622, 627794, 729314, 777992, 1108214, 1163629 There are about 300 candidates below n=1.1M still untested but the gap after 777992 more than 320k wide will most likely remain. And at n=30M you can expect much larger gaps. So I think it's the best to reconsider your selection of k and n. If you want to stick with k=27 I'd suggest a range of n going at least to 40M. 
20080516, 01:02  #4 
Oct 2007
Manchester, UK
17×79 Posts 
masser, using the same method that Prime95 uses to calculate odds, and assuming that the sieve will proceed until only 2^50, and working with the largest exponant remaining in the sieve 33554422, I calculate the odds to be:
50 / 16,777,213.377 = 1 in 335,544 that any single candidate is prime. Alternately, based on an average density of primes log(exponant), I come to the expected figure of 1/23.3 primes in the range, and assuming 14,000 candidates left after sieving (I think this is a high estimate), that would put the chance any individual candidate is prime at 1 in 319,150. So yes, there is a high chance of failure for this particular range, I guess in that case we would do what GIMPS do and move on to a higher range. Individually speaking though, the odds are very similar to (if not a little better than) the odds of finding a prime with GIMPS. It is very likely that the first known 10 million digit prime will be found as part of GIMPS, but wouldn't it be something if it wasn't? And even if the first is a Mersenne, to see a nonMersenne prime slot in a number 2 would be a nice break from tradition. Some people just like to find primes full stop, so they stick to the smaller exponants, some people like to find large primes so they may search among numbers with over a million digits, and some people like to search for staggeringly HUGE primes with over 10 million digits, knowing that the odds against finding them are exceedingly slim. This project would be for people in that last group. Kosmaj, I agree that the range is quite small, and so the odds are against there being a prime within it. In fact I think that there is a 4.29% chance of finding a prime in this range. However, in order to keep the sieve reasonably fast, I chose a smaller range. Despite the small range though, there are still a lot of candidates to test, so even with a lot of interest it will take a long time to crunch through all of the exponants. If there is enough of an effort made with LLRing to get through all of those candidates, then there will be far and away enough participants to sieve a much larger range for further testing. As far as the choice of k, I have already done a quick test of iteration times. For k=3 I had an iteration time of 48.7ms, and for k=27 I had a time of 48.9ms, a 0.41% increase. Even on the largest exponant in the range, that would only make a 1hour 40min difference in run time. I did the test on a Core 2 Duo E6600, on which a test would take 19 days. Last fiddled with by lavalamp on 20080516 at 01:05 
20080516, 15:50  #5 
"Curtis"
Feb 2005
Riverside, CA
2^{2}×7×13^{2} Posts 
Lava
Run times for k=3 vs k=27 will be identical for some values of n, and quite a bit different for other values of n, as the FFTlength jumps up at lower n for larger k's. You tested k=3 vs k=27, and learned you are in a "lucky" range where they are identical. However, if you do ever expand to a larger nrange with a larger chance to find a prime, kosmaj's advice becomes more relevant. Perhaps it's worth learning what n has a jump in FFT length (thus iteration time)? I imagine the jump will be 15% or more. If that happens 500k sooner for k=27 than k=3, that band of exponents "wastes" 15% of LLR time compared to selecting k=3. In short, your current project is equally good on 27 as 3. Happy hunting! Curtis 
20080516, 18:42  #6 
Oct 2007
Manchester, UK
17×79 Posts 
I took your advice and investigated where the next increase is. For k=3 and k=27 over the entire range I'm sieving, the FFT length is 2^21. The FFT length stays the same all the way up to n=34,514,134 for k=27 and up to n=37,838,044 for k=3.
So if and when the first batch of candidates are all sieved and LLRed, perhaps 27 and a couple of other small ks that sieve well could be searched up to their next FFT length jump. This would be the most efficient way to find 10m digit primes aside from the Mersennes. 
20080517, 13:58  #7 
Mar 2004
381_{10} Posts 
I recommend sieving a rectangular area like k=349 for a smaller area of n with k*2^n+1 and k*2^n1 together.
This reduces the performance disadvantage of vertical sieving. Note that the k range cannot be too large depending on the chosen n range in order to prevent larger FFT sizes. See older discussion at: http://www.mersenneforum.org/showthread.php?t=6449 and http://www.mersenneforum.org/showthread.php?t=5959 Are there any improved implementations for the Generalized fermat number search (after Proth) that are optimized for the newer computer architecteres (at least SSE2)? 
20080517, 15:18  #8 
"Curtis"
Feb 2005
Riverside, CA
2^{2}×7×13^{2} Posts 
as far as I know, sr2sieve does not sieve both riesel and proth numbers together. I believe using an older program to achieve this costs more than it gains.
since such a sieve would run for CPUyears, it would pay to build a 20k narrow sieve and a 1k wide sieve and see which is faster for a given number of candidates (not faster speed, but faster premoval). If sieve resources are limited, it may make sense to pick a number of candidates for which you are willing to sieve to 1q (sounds like this is what you did for this first effort). It's silly to build a superefficient sieve and then give up early because you want to move on to LLR testing. Curtis 
20080517, 15:21  #9 
Nov 2003
2·1,811 Posts 
48ms per iteration means about 19 days to complete one test at n=33.3M. What kind of machine are you using? Sounds like a fast one.
Does somebody know where is GIMPS (40M ?) and how long does it take to complete one test on a modern cpu. 
20080517, 15:40  #10  
A Sunny Moo
Aug 2007
USA (GMT5)
3×2,083 Posts 
Quote:
To start such a sieve, just specify the sequences for both sides to srsieve in the usual manner, making sure of course to use the "a" option to specify that you want to save your sieve file in ABCD format. 

20080517, 16:19  #11  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:
If the time is about the same as GIMPS's times for a number of the same size (I think Prime95 is faster, but just theoretically) that would be a 2048K FFT size and 48 ms would be around a Core 2 Duo E6600 at standard clock of 2400MHz. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Million digit moonshot  MooMoo2  Twin Prime Search  9  20171223 17:36 
When will the first 10 million digit prime be reported?  Uncwilly  Lounge  13  20090722 13:56 
Deep Sieving 10m Digit Candidates  lavalamp  Open Projects  53  20081201 03:59 
k = 2 thru 31 Ten Million Digit numbers  TTn  15k Search  4  20040821 18:20 
100 MILLION DIGIT NUMBER  lpmurray  Software  8  20040531 19:22 