Extrapolation: How long until the minimum megaprime?

[CRGreathouse]

Originally Posted by science_man_88

I see ways to limit the values it could be significantly I think.

2+4+2+4+2 = 14
4+2+4+2+4+2+4+2+4 =28

using these 2 after finding a n such that 10^x+n is 0 mod 7 can eliminate all multiples of 7. this would remove about 2/42 candidates ( in the range of 9* 10^999999 range before 10^1000000, that's quite a few).

Right -- or more generally, you can sieve out all numbers with a prime multiple less than some fixed constant, like I suggested in the original post. It may be worthwhile to do other sorts of testing for small prime factors, I'm not sure. But at the end you're still going to have to do a lot of Miller-Rabin tests (or something similar) to weed out the many composites that will remain.

[science_man_88]

Originally Posted by CRGreathouse

Right -- or more generally, you can sieve out all numbers with a prime multiple less than some fixed constant, like I suggested in the original post. It may be worthwhile to do other sorts of testing for small prime factors, I'm not sure. But at the end you're still going to have to do a lot of Miller-Rabin tests (or something similar) to weed out the many composites that will remain.

I'm finding a pattern ( oops shouldn't of said that) in the multiples depending on what version ( 6n+1 or 6n-1) they are that helps of course if we can do this further up we can do it further down and build supporting primes.

[science_man_88]

(22:41)>c=[];forstep(x=1,30,[2,4],c=concat(c,[x]));forprime(y=3,3000,for(z=1,#c,if((10^999999+c[z])%y==0,c[z]=0)));c=vecsort(c,,8);c=vector(#c-1,n,c[n+1])
%74 = [3, 7, 9, 13, 21]

This is what I can think of I know it's not ideal or fast.

[KEP]

Hello Folks, I saw this forum thanks to a link from www.worldofnumbers.com, and I just wanted to let you all know, that I have started a search for the first megaPRP. I'm at current time at p~=9.6G, and have about 122860 candidates remaining. When I reaches 10G in <2 days, the next approach will be to sieve to p=100G. This effort alone requires:

90,000,000,000 p : 2880 p/sec = 31,250,000 CPU seconds on a Q6600 2.4 GHz. Optimal sievedepth will be at least 2T.

The testing are actually quite easy. So it doesn't take much skill to do this search however it aquires a huge amount of resources, so if you care to join in, please PM me and I'll guide you through the few steps nescessary to help out in this effort. The sieve reservations will open up at p=10G, and I would like if you requested sieve ranges of at least p=5G, wich will take you about 6 days on a Q6600 2.4GHz. Maybe when it gets practical, we will be able to convince the primegrid folks to help out with the sieving.

Btw, the search for the first MegaPRP of the following form is: 10^999999+y

y ranging from 1 to 4,999,999

Testingtimes range starts at ~4 hours/candidate and ends at ~34.5 hours on a Q6600 2.4GHz, and at current sievelevel, the removal rate is 1 candidate every 620 seconds, so we are far from optimal sievedepth.

Well long story short, if you wanne help out, please let me know.

Take care

Kenneth Pedersen

[axn]

Originally Posted by KEP

Hello Folks, I saw this forum thanks to a link from www.worldofnumbers.com, and I just wanted to let you all know, that I have started a search for the first megaPRP. I'm at current time at p~=9.6G, and have about 122860 candidates remaining. When I reaches 10G in <2 days, the next approach will be to sieve to p=100G. This effort alone requires:

90,000,000,000 p : 2880 p/sec = 31,250,000 CPU seconds on a Q6600 2.4 GHz.

WTH? You should be doing something like 10T / day. What are you using to do the sieving?

[KEP]

Originally Posted by axn

WTH? You should be doing something like 10T / day. What are you using to do the sieving?

I'm currently using srsieve. If you are aware of any program that can do 10T a day, please let me know. I tried to ask around, but found no one who knew of any other programs beside srsieve. It appears that you know of such a program, so let me hear what you have to offer.

Thanks

Kenneth

[TimSorbet]

Originally Posted by KEP

I'm currently using srsieve. If you are aware of any program that can do 10T a day, please let me know. I tried to ask around, but found no one who knew of any other programs beside srsieve. It appears that you know of such a program, so let me hear what you have to offer.

Thanks

Kenneth

With the -d flag, sr2sieve can sieve numbers of the form b^n+/-k (which is what you've got). I'm not sure if that's the best way to sieve, but it's probably much faster than srsieve.

[KEP]

Originally Posted by Mini-Geek

With the -d flag, sr2sieve can sieve numbers of the form b^n+/-k (which is what you've got). I'm not sure if that's the best way to sieve, but it's probably much faster than srsieve.

Well I tried to use sr2sieve with the -d and with and without the building of legendre symbol tables, most of the times it stated that sr2sieve had encounted a program error and then windows began to collect data such that windows could eventually offer a solution. If I could somehow get sr2sieve to sieve all 122xxx candidates at once, without it crashing, it actually might be faster. However if you think you have a solution, please let me know, because it would be nice to sieve more than 970 M/day, even though I'm not sure it is feasible to shoot for 10 T/day, but let's see what Axn has to offer

Thanks for your suggestions and feedback.

Kenneth

[axn]

Originally Posted by KEP

Well I tried to use sr2sieve with the -d and with and without the building of legendre symbol tables, most of the times it stated that sr2sieve had encounted a program error and then windows began to collect data such that windows could eventually offer a solution. If I could somehow get sr2sieve to sieve all 122xxx candidates at once, without it crashing, it actually might be faster. However if you think you have a solution, please let me know, because it would be nice to sieve more than 970 M/day, even though I'm not sure it is feasible to shoot for 10 T/day, but let's see what Axn has to offer

Thanks for your suggestions and feedback.

Kenneth

I believe newpgen has a "b^n+k" (with fixed n -- not variable n which srsieve offers) mode which can be used for this -- however, I cannot confirm this since newpgen keeps crashing on my Win7 box. If not, a custom sieve will have to be written. Perhaps Geoff /Ken_g6/bsquared can help.

But if you're not doing at least 8T-10T/day, there is something drastically wrong. This is based on the fact that b^n+k (fixed n) sieve should be as fast as k*b^n+1 (fixed n) sieve.

If nothing else, I can write a slow poke sieve in Pari/GP, which should be 100 times faster than what you're getting right now.

[KEP]

Originally Posted by axn

I believe newpgen has a "b^n+k" (with fixed n -- not variable n which srsieve offers) mode which can be used for this -- however, I cannot confirm this since newpgen keeps crashing on my Win7 box. If not, a custom sieve will have to be written. Perhaps Geoff /Ken_g6/bsquared can help.

But if you're not doing at least 8T-10T/day, there is something drastically wrong. This is based on the fact that b^n+k (fixed n) sieve should be as fast as k*b^n+1 (fixed n) sieve.

If nothing else, I can write a slow poke sieve in Pari/GP, which should be 100 times faster than what you're getting right now.

Unfortunantly NewPGen only has a b^n+k (with fixed k) function. This one however seems to constantly crash, on my Dual Core as well as it did on my dual cores predecessor (the computer I had before my dual core). I'm not sure Geoff can be of any help, since he appears to have left the building. Ken_g6 may have other interests. However I'm thinking that maybe Rogue can develop an optimized siever. But for now, I think that I'll take you up on your offer and see if you can make a siever for me. Can you make it just as userfriendly as srsieve, sr2sieve and all other of Geoffs sievers? Even 100 times would mean that I would be able to sieve approximately 100G/day or about 1.2M p/sec.

Well let me hear what you think, for now I'll go home and try to use NewPGen on my Quad core and see if NewPGen also crashes on that one.

Thanks for your feedback

Take care

Kenneth

[axn]

Originally Posted by KEP

Unfortunantly NewPGen only has a b^n+k (with fixed k) function.

Hmmm. Don't forget to look up & down that list -- there may be more than one b^n+k.

Originally Posted by KEP

This one however seems to constantly crash, on my Dual Core as well as it did on my dual cores predecessor (the computer I had before my dual core).
<snip>
Well let me hear what you think, for now I'll go home and try to use NewPGen on my Quad core and see if NewPGen also crashes on that one.

Dang. Does it crash as soon as it starts (that's been my problem)? Good luck with the quad core.

Anyway, if you don't have any further luck with NewPGen, I'll try to put something together.

PS:- Try contacting bsquared. He's written most of the basic low-level routines, and has implemented kick ass SoE. So it'd be a trivial thing for him to put together a state-of-the-art sieve for this problem.