mersenneforum.org Sieving for 10M prime for odd k, 3-31
 Register FAQ Search Today's Posts Mark Forums Read

 2006-10-13, 03:11 #1 jasong     "Jason Goatcher" Mar 2005 3×7×167 Posts Sieving for 10M prime for odd k, 3-31 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^n-1, 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 n-value. 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^n-1 starts being more than 10 million digits. What I propose is that we take the odd ks 3-31 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.
2006-10-13, 04:22   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

There's been some discussion of this. On a quick search I found:

At what sizes of exponent n (> 33219280) does an L-L test on 2n-1 take the same time as sieving/testing a 10-million-decimal-digit k*2m-1 for odd k from 3 to 31?

Quote:
 After passing ~M38000000 it is more efficient to find 10M digits primes of the form k*2^n+1 or k*2^n-1

Last fiddled with by cheesehead on 2006-10-13 at 04:28

 2006-10-13, 04:23 #3 paulunderwood     Sep 2002 Database er0rr 361710 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 2006-10-13 at 04:27
2006-10-13, 04:43   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

Quote:
 Originally Posted by paulunderwood Remember that you would need quite a few computers to rival GIMPS'.
But consider the point of view of the individual mercenary participant: At what point (size of exponents currently being assigned by PrimeNet) is it advantageous for me to switch from GIMPS to the k*2n+-1 search for the purpose of maximizing my probability per unit of time of finding a 10M-digit EFF-prize-winning prime?

Now, if I'd find it satisfying merely to be a participant in the group that first finds a 10M-digit prime, then perhaps I should continue in GIMPS.

But if I'm just after the money for myself, at some point k*2n+-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 2006-10-13 at 05:04

 2006-10-13, 05:02 #5 paulunderwood     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 P-1 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 2006-10-13 at 05:07
 2006-10-13, 05:20 #6 jasong     "Jason Goatcher" Mar 2005 1101101100112 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 n-values would be used? (For the record, I sieved up to 1e9 for odd k, 7-31, 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)
 2006-10-13, 05:27 #7 jinydu     Dec 2003 Hopefully Near M48 6DE16 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.
 2006-10-18, 19:57 #8 jasong     "Jason Goatcher" Mar 2005 1101101100112 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 2006-10-18 at 19:58
2006-10-18, 20:00   #9
axn

Jun 2003

114458 Posts

Quote:
 Originally Posted by jasong 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?
proth_sieve or JJSieve will be able to sieve multiple k's simultaneously (these are the programs used by SoB, PSP and RieselSieve projects).

2006-10-18, 21:48   #10
jasong

"Jason Goatcher"
Mar 2005

3·7·167 Posts

Quote:
 Originally Posted by axn1 proth_sieve or JJSieve will be able to sieve multiple k's simultaneously (these are the programs used by SoB, PSP and RieselSieve projects).
The reason I mentioned the sieving individual k/n pairs is that people are more familiar with that, and the credit system is already in place.

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,281-33,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 bit-depth 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 2006-10-18 at 21:51

 2006-10-18, 22:25 #11 paulunderwood     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 prize-winning Mersenne. Based on how many non-mersenne 10M digit numbers you can test in say a year -- if that is the expected time to the next Mersenne -- and sieve for about 3-5% 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 2006-10-18 at 22:33

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 JHansen NFSNET Discussion 9 2010-06-09 19:25 jasong Lone Mersenne Hunters 200 2008-10-29 13:21 jasong Software 20 2007-11-28 03:48 jasong Math 18 2006-03-31 03:14

All times are UTC. The time now is 23:10.

Mon Apr 12 23:10:30 UTC 2021 up 4 days, 17:51, 1 user, load averages: 2.14, 2.25, 2.52