20061013, 03:11  #1 
"Jason Goatcher"
Mar 2005
3×7×167 Posts 
Sieving for 10M prime for odd k, 331
I just thought I'd throw this out there. I figured if people were willing to sieve for the billion digit project, they might like this too.
Most people realize that the GIMPS numbers that we deal with are basically k*2^n1, and GIMPS is concentrating on k=1. The reason for this is that the modular arithmetic is fastest when you're dealing with a power of two, minus 1. Here's the thing, we aren't concentrating on any particular number, we're basically attempting to find a prime with more than 10 million digits. So any 10 million digit prime will do. Now, let's look at that k. I've been told, I don't know officially, that for k=3 to 31, each iteration takes slightly longer than if k equaled 1 for that particular nvalue. So, if GIMPS is unlucky, it's entirely possible that a person's chances to find a 10 million digit will increase if they pick an odd k from 3 to 31 and start with an n at or above 33,219,281, the place 2^n1 starts being more than 10 million digits. What I propose is that we take the odd ks 331 and start a group sieving effort in anticipation of the possibility that those ks will later be desired in the search for a 10 million digit prime. I know it's entirely possible that I've overlooked something that makes this a fool's errand, but I just thought I'd throw this out there for people to chew on. 
20061013, 04:22  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
There's been some discussion of this. On a quick search I found:
http://www.mersenneforum.org/showthread.php?t=1108 http://www.mersenneforum.org/showthread.php?t=2379 http://www.mersenneforum.org/showthread.php?t=5959 At what sizes of exponent n (> 33219280) does an LL test on 2^{n}1 take the same time as sieving/testing a 10milliondecimaldigit k*2^{m}1 for odd k from 3 to 31? In the third thread linked above (t=5959), biwema states Quote:
Last fiddled with by cheesehead on 20061013 at 04:28 

20061013, 04:23  #3 
Sep 2002
Database er0rr
3617_{10} Posts 
Why not do odd k=3..31 for k*2^n+1 as well?
Remember that you would need quite a few computers to rival GIMPS'. Also sieving would have to be done to a great level too. Last fiddled with by paulunderwood on 20061013 at 04:27 
20061013, 04:43  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
7692_{10} Posts 
Quote:
Now, if I'd find it satisfying merely to be a participant in the group that first finds a 10Mdigit prime, then perhaps I should continue in GIMPS. But if I'm just after the money for myself, at some point k*2^{n}+1 becomes a better bet, and the tipping point might be lowered by considering that I'd not have to split the EFF prize via George's formula (unless the author of software that I, the example mercenary, use has added a license clause like George's  which I, cheesehead, would applaud). Last fiddled with by cheesehead on 20061013 at 05:04 

20061013, 05:02  #5 
Sep 2002
Database er0rr
3,617 Posts 
That is the 64 thousand dollar question  or should I say 100 thousand dollar question?
* GIMPS has been lucky recently? * Mersennes exponents are only prime. * DWT becomes increasingly more time consuming per test as k grows * with no sieving, trial division for each candidate with k>1 still requires a considerable effort  plus P1 testing * other things I have failed to appreciate (isn't LLR covered by GW libs w.r.t. the EFF prize?) Last fiddled with by paulunderwood on 20061013 at 05:07 
20061013, 05:20  #6 
"Jason Goatcher"
Mar 2005
110110110011_{2} Posts 
So, would people be interested in sieving these numbers? If not now, maybe in six months to a year from now?
Also, assuming it's all odd k from 3 to 31(15 of em), what range of nvalues would be used? (For the record, I sieved up to 1e9 for odd k, 731, for n=33,219,281 33,319,281 and for 3 and 5, n=33,219,281 34,219,281. In case anybody's interested, I can list the number of k/n values left after that. I figure if we want a certain number of candidates, we can use my results to figure out which n to go up to from n=33,219,281) 
20061013, 05:27  #7 
Dec 2003
Hopefully Near M48
6DE_{16} Posts 
I see what you mean. At some point, GIMPS will have tested all Mersenne numbers "slightly" greater than 10 million digits. Thus, by trying a different value of k, one can test numbers closer to 10 million digits, that are hence smaller.

20061018, 19:57  #8 
"Jason Goatcher"
Mar 2005
110110110011_{2} Posts 
If people aren't willing to do a group sieving effort, how about an individual factoring effort?
Would it be difficult for the creator of Prime95 to change the code to sieve other k's? Last fiddled with by jasong on 20061018 at 19:58 
20061018, 20:00  #9 
Jun 2003
11445_{8} Posts 
proth_sieve or JJSieve will be able to sieve multiple k's simultaneously (these are the programs used by SoB, PSP and RieselSieve projects).

20061018, 21:48  #10  
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
Quote:
In order for it to be effective, the k/n pairs would have to be sieved to a high bit depth, and at the higher bit levels sieved pairs will be few and far between. Because of this, I recommend we come up with a scoring system that goes by amount sieved AND number of k/n pairs removed. Below, I've listed how many k/n pairs are left for each k after sieving to 1e9, for both plus and minus for 33,219,28133,319,281: minus 1 3 9228 5 6719 7 2864 9 5108 11 2495 13 3178 15 6971 17 7424 19 4102 21 6474 23 4365 25 5136 27 7093 29 1480 31 6682 plus 1 3 6765 5 2796 7 6767 9 7263 11 4192 13 2996 15 9015 17 2026 19 2610 21 7134 23 2492 25 6552 27 7577 29 6658 31 2357 So, hopefully, after we come up with approximately how many k/n pairs we want at the end, someone will do the math, and sieve alone to a good level. And then we can do distributed sieving, just like SOB and Riesel Sieve. Question: Can the sieving program(I assume JJSieve) handle both plus and minus 1, or do we have to make a choice? Edit: What bitdepth are we going for? Since it's distributed, we can be more specific about how high to go, I guess. Last fiddled with by jasong on 20061018 at 21:51 

20061018, 22:25  #11 
Sep 2002
Database er0rr
3,617 Posts 
Nice to see 321 being the heaviest, besides being the quickest test
What you got to ask yourself is how much computing are your going to put into this, in the hope of finding something before the 70,000 GIMPS computers will probably find their next, the EFF prizewinning Mersenne. Based on how many nonmersenne 10M digit numbers you can test in say a year  if that is the expected time to the next Mersenne  and sieve for about 35% of that time. Hypothethically, if you were going to use LLR on 50 computers for a year, thereby LLR'ing 50*12 numbers  i.e 600 numbers tested per year  then you would want to sieve on 50 computers for 3 weeks, and your initially range would be the average of those numbers you obatained a weight for  say that's about 5%. Therefore your range for 50 computers for one year would be 600*20/30 == 400. If you think GIMPs is in for some back luck for a change you can adjust the figure of GIMPS' e.t.a. on M45 accordingly. I know what you're thinking: 'Did GIMPS find six prime (recently) or only five?' Well, to tell you the truth, in all this excitement, I've kinda lost track myself. But being there was found M44, the biggest prime in the world, and would blow your head clean off, you've got to ask yourself one question: 'Do I feel lucky?' Well, do ya, punk? Last fiddled with by paulunderwood on 20061018 at 22:33 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
Alternative Sieving for 10M digit prime search  jasong  Lone Mersenne Hunters  200  20081029 13:21 
twin prime, but sieving n instead of k. Possible?  jasong  Software  20  20071128 03:48 
prime density vs. sieving vs. prp time  jasong  Math  18  20060331 03:14 