Newpgen worthwhile for n*2^n+/-1 numbers?

[jasong]

PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).

I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).

[rogue]

Originally Posted by jasong

PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).

I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).

Your thread title and thread text do not belong together. If you have paid any attention to PrimeGrid, you would know that n*2^n+/-1 are known as Cullens and Woodalls. Also, if you have paid any attention to the PrimeGrid message boards you would know that you need to use a combination of MultiSieve and gcwsieve to sieve numbers of this form.

BTW, I also gave Geoff the code so that gcwsieve would not need to rely on MultiSieve for the initial sieving, but AFAIK, he has not implemented it.

[axn]

NewPGen cannot handle these series. It can do "fixed-n variable-k" or fixed-k variable-n" sieves, but Cullen-Woodalls are "variable-n variable-k" (ok, well n /is/ the k), and so NewPGen can't.

I am aware of only two publicly available programs -- rogue's multisieve and geof's gwcsieve -- that can handle these series. And the latter is being used by PrimeGrid.

EDIT:- Beaten to the post by rogue :)

[jasong]

I don't think you two considered my post for much longer than it took to skim it. 10G in a minute and a half is nothing to sneeze at, and you'll note that I was informed enough about gcwsieve to know that it had gotten to about 2^33 using PrimeGrid software(I suppose I didn't state that last part straight out, but I think it would be kind of obvious to someone who was knowledgeable of the sieving scene in general, given a little thought)

So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.

[rogue]

Originally Posted by jasong

I don't think you two considered my post for much longer than it took to skim it. 10G in a minute and a half is nothing to sneeze at, and you'll note that I was informed enough about gcwsieve to know that it had gotten to about 2^33 using PrimeGrid software(I suppose I didn't state that last part straight out, but I think it would be kind of obvious to someone who was knowledgeable of the sieving scene in general, given a little thought)

So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.

Are you asking if it is faster to take a specific n and sieve it deeper? The easy answer is "No". There is an economy of scale in doing many n concurrently. By doing fewer n, the factor removal rate goes down considerably. Based upon my knowledge, doubling the sieving depth will give you a 3% chance of finding a factor. If you can quadruple the sieving depth in the same amount of time it takes to do a PRP test, then the PRP test is clearly what you want to do.

BTW, I believe that gcwsieve will be faster than NewPGen for a single n, but only testing that hypothesis will prove it to be correct.

[jasong]

Ok, thanks for the answer, and sorry for my stiff response. 10G in a minute thirty seemed fast to me and I didn't think that that had been noticed.

[axn]

Originally Posted by jasong

I don't think you two considered my post for much longer than it took to skim it.

Mea culpa. I am so used to thinking NewPGen used for sieving a series that I didn't even register your question.

Originally Posted by jasong

So, I'll restate my question, which I don't consider answered. Does anyone think it would be worthwhile to take the various numbers individually higher using NewPGen, like say, a bit-level or two. Or, maybe not even a bit level.

Ok, let's plugin the numbers.

90 seconds to 2^34 - 2.9% chance of factor.
270 seconds to 2^35 - 5.7% chance of factor.
630 seconds to 2^36 - 8.3% chance of factor
1350 seconds to 2^37 - 10.8% chance of factor

Breakeven points (i.e., how long must an LLR test take for these to be worthwhile).

To 2^34: 90 + (1-2.9%)*t = t ==> t = 90/.029 = 3100 sec.
To 2^35: t = 270/.057 = 4700 sec
To 2^36: t = 7500 sec
To 2^37: t = 12500 sec.

So, depending on the t value (LLR test time), you can decide how far you can sieve. NOTE that these are /breakeven/ points -- the optimal sieving point will be somewhat lesser (or alternately, the LLR test time should be greater than what is indicated)

[geoff]

Originally Posted by jasong

PrimeGrid has finished their sieving and they only got up to about 2^33(a little under 8.6G).

I don't think this is right, my current manual reservation is 6300G-6400G, much higher than 2^33.

I'm wondering if it would be a good idea to throw newpgen at these numbers? And, if, so, how high should I go? Also, I'm running Linux, and I've heard that newgen can be run commandline under Linux, is that true? I tried a number and it was banging along at about 10G every 1:30(m:s).

That is 90sec for one number? You are using NewPGen with a one-line input file?

My 2.88GHz Celeron is sieving about 58,000 numbers for PrimeGrid at the rate of about 46,000 p/sec. That is equivilent to 240G for one number in 90 sec. Unless your machine is 24 times slower than mine, you are wasting your time.

[jasong]

Thanks for the response, and sorry for the harsh words. I'm positive I've rushed to respond to something I didn't read adequately in the past, I just can't think of anything in particular. In the meantime, I need to Google 'mea culpa' to find out precisely what it means, since I'm only familiar with the context it's used in and not the precise meaning.

[jasong]

Originally Posted by geoff

I don't think this is right, my current manual reservation is 6300G-6400G, much higher than 2^33.



That is 90sec for one number? You are using NewPGen with a one-line input file?

My 2.88GHz Celeron is sieving about 58,000 numbers for PrimeGrid at the rate of about 46,000 p/sec. That is equivilent to 240G for one number in 90 sec. Unless your machine is 24 times slower than mine, you are wasting your time.

Um, Geoff, there's more than one one sieving effort that's been going on at PrimeGrid. Actually, over it's short life, there have been three separate sieving projects for three separate objectives, (1) Cullen/Woodall sieving, which uses gcwsieve, which is the best method, at least for the lower p-values (and this is the project I'm talking about),(2) twin prime search, which involves n=333,333 at the moment, and involved n=195,000 in the past, and (3) what you're involved in, which is the Sierpinski sieve, which helps both the Prime Sierpinski project and the Seventeen or Bust project which have some overlapping and nonoverlapping k's in their initiatives.

[axn]

Originally Posted by jasong

Um, Geoff, there's more than one one sieving effort that's been going on at PrimeGrid. Actually, over it's short life, there have been three separate sieving projects for three separate objectives, (1) Cullen/Woodall sieving, which uses gcwsieve, which is the best method, at least for the lower p-values (and this is the project I'm talking about),(2) twin prime search, which involves n=333,333 at the moment, and involved n=195,000 in the past, and (3) what you're involved in, which is the Sierpinski sieve, which helps both the Prime Sierpinski project and the Seventeen or Bust project which have some overlapping and nonoverlapping k's in their initiatives.

LOL. Now you gone done it Sierpinski sieve is running at at least a 1000 times higher values than what geoff said. And I'm pretty sure, considering that geoff wrote 2 out of 3 of those sieve programs that he knows what he's talkin about

Ah, here is the thread in question -- looks like the sieve reservation has reached 2^43.

[PS:- I must be having a really off day -- getting a C/W sieve to 2^33 is like a week's job on a single PC]