mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2006-10-13, 03:11   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default 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.
jasong is offline   Reply With Quote
Old 2006-10-13, 04:22   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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 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?

In the third thread linked above (t=5959), biwema states
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
cheesehead is offline   Reply With Quote
Old 2006-10-13, 04:23   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

361710 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2006-10-13, 04:43   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
cheesehead is offline   Reply With Quote
Old 2006-10-13, 05:02   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2006-10-13, 05:20   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

1101101100112 Posts
Default

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)
jasong is offline   Reply With Quote
Old 2006-10-13, 05:27   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

6DE16 Posts
Default

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.
jinydu is offline   Reply With Quote
Old 2006-10-18, 19:57   #8
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

1101101100112 Posts
Default

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
jasong is offline   Reply With Quote
Old 2006-10-18, 20:00   #9
axn
 
axn's Avatar
 
Jun 2003

114458 Posts
Default

Quote:
Originally Posted by jasong View Post
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).
axn is offline   Reply With Quote
Old 2006-10-18, 21:48   #10
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

Quote:
Originally Posted by axn1 View Post
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
jasong is offline   Reply With Quote
Old 2006-10-18, 22:25   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

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 2016-05-06 08:13
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
Alternative Sieving for 10M digit prime search jasong Lone Mersenne Hunters 200 2008-10-29 13:21
twin prime, but sieving n instead of k. Possible? jasong Software 20 2007-11-28 03:48
prime density vs. sieving vs. prp time 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.