Possible loophole/bug in NPG 2.82 ???

Tumo · 2005-01-31, 02:12

Please forgive my being a novice, but i stumbled onto either a user error
(which i suspect is most likely) or a possible problem with NPG (hard to believe one could exist).

NPG, Dec 2004 version...

try k.b^n-1 with k fixed

enter b=2, k=7 nmin=2, nmax=65536 and run (with or w/o verify)

@P= 2G, stop the sieve... examine the output file.. you will find something
like:

2256610126:M:0:2:258
7 29
7 45
7 101
7 177

now start again, and notice the Nmin window has updated from 2 to 29.

At some point above 4G (I stopped closer to 6G)... stop the sieve again.

examine the output files.

I find this:

6426074968:M:0:2:258
7 45
7 101
7 177

I have verified this condition on both AMD64 FX and Intel P4b (both are SSE2 machines)... both on Win/XP.. AMD on SP1, P4 on SP2.

7*2^29-1 is valid from everything I've seen, listed in the forums and shows
up valid by LLR 3.3.

Also, i believe other values lower than 29 are missing, true?

I tripped over this after the recommended 24+ hours of sieving for an LLR run. I had crossed well over 250G at that point... When I ran the numbers, NOTHING came up prime. According to the period/frequency of the prime, I should have had several hits.

I went to the 'Riesel < 300' page, selected a test range for others and did it again, and again... then went back to basics which brings me here.

May I ask what it is I am tripping over? I am stumped.

I thank you for your time and tolerance.

I also thank you in advance for your assistance.

Chuck

Jean Penné · 2005-01-31, 09:01

Quote:

Originally Posted by Tumo

Please forgive my being a novice, but i stumbled onto either a user error
(which i suspect is most likely) or a possible problem with NPG (hard to believe one could exist).

NPG, Dec 2004 version...

try k.b^n-1 with k fixed

enter b=2, k=7 nmin=2, nmax=65536 and run (with or w/o verify)

@P= 2G, stop the sieve... examine the output file.. you will find something
like:

2256610126:M:0:2:258
7 29
7 45
7 101
7 177

now start again, and notice the Nmin window has updated from 2 to 29.

At some point above 4G (I stopped closer to 6G)... stop the sieve again.

examine the output files.

I find this:

6426074968:M:0:2:258
7 45
7 101
7 177

I have verified this condition on both AMD64 FX and Intel P4b (both are SSE2 machines)... both on Win/XP.. AMD on SP1, P4 on SP2.

7*2^29-1 is valid from everything I've seen, listed in the forums and shows
up valid by LLR 3.3.

Also, i believe other values lower than 29 are missing, true?

I tripped over this after the recommended 24+ hours of sieving for an LLR run. I had crossed well over 250G at that point... When I ran the numbers, NOTHING came up prime. According to the period/frequency of the prime, I should have had several hits.

I went to the 'Riesel < 300' page, selected a test range for others and did it again, and again... then went back to basics which brings me here.

May I ask what it is I am tripping over? I am stumped.

I thank you for your time and tolerance.

I also thank you in advance for your assistance.

Chuck

When sieving in fixed k mode, Newpgen eliminates a value when it finds itself
as a divisor !

For example :

7*2^29-1 = 3758096383 is prime, but is eliminated when the sieve reaches
this prime value and tries it as a divisor, etc...
This drawback only occurs for tiny values of n, less than 64, so the best
thing to do is starting the sieve for n = 64 and test the primality for all
n values below, which is very fast !

I hope this can help you...

Regards,

Jean

Keller · 2005-01-31, 10:16

But this is a serious bug and might have caused lots of problems ...
For example Rieselsieve, PSP or SoB ...
Maybe values of n have been missed that are smaller than n=64 and maybe they are wasting lots of work because a tiny number has been missed ... Who knows ;)

em99010pepe · 2005-01-31, 10:52

Hello,

Yesterday I noticed that too. I wanted to reserve a Sierpinsksibase4k=63411 but I first run newpgen 2.82 to see the size of the outputfile.

k=63411; base=4; nmin=10000, nmax=100000
The first run gave me this:

16738300:P:0:4:257
63411 10000
63411 10016
63411 10076
63411 10140
63411 10196
63411 10212
63411 10256
63411 10292
63411 10302
63411 10307
63411 10308
63411 10313
63411 10317
63411 10320
63411 10322
63411 10326
63411 10331
63411 10337
63411 10338
63411 10352
63411 10353
63411 10361
63411 10362
63411 10365
63411 10370
63411 10377
63411 10380
63411 10385
63411 10388
63411 10395

And the second one this:

36278740:P:0:4:257
63411 10016
63411 10076
63411 10140
63411 10196
63411 10212
63411 10256
63411 10292
63411 10320
63411 10400

I still have both files.

Cheers,

Carlos

2005-01-31, 12:11

Quote:

Originally Posted by Keller

But this is a serious bug and might have caused lots of problems ...
For example Rieselsieve, PSP or SoB ...
Maybe values of n have been missed that are smaller than n=64 and maybe they are wasting lots of work because a tiny number has been missed ... Who knows ;)

LOL, you really think noone has tested n values less than 64 until now. Man, i bet this was done hundreds of times, with many software. And most of that can even be done by hand! there really are no primes for sob, riesel, psp and so on...

Tumo · 2005-02-01, 00:56

I can understand the low value situation easily and accept that.

I present to you this:

K=237, Base=2, Nmin=524288, Nmax=1048576, k.b^n-1 with fixed k.

The same 'collapse' occurs. Understanding that it's a recursive condition of not eliminating an N (aka K/N pair).. and then having that same N (K/N pair) be removed by a higher value P. It is easy for me to sieve up to P = 1 Tera in 24 hours or so.

Given this to make perfect sense, at what 'P' value does one stop sieving?

I sieve for 24 hours , as commonly recommended, and this usually puts me in the High-'G' range. Is it common and reasonable to expect that only the largest N of that sieve, regardless of P,K, or N ranges set at the start, will be left? It seems this is a recursive factorization issue and I see now that I should probably rephrase my initial question to be:

"for a given K, sieving in a particular range of Nmin->Nmax, at what point do you tell a novice when to stop the sieve and simply 'bite the bullet', running PRP/LLR on all remaining N in the file (including the N that would have been removed if P were to run higher)?"

Sorry if I am being thick (slow to learn) about this, I am just trying to understand the relationships that you all have had great experience with. I can sieve at a very fast speed, but my LLR time is embarassingly slow, hence my desire to remove as many N as possible and reasonable.

Thanks for all the advice.
Thanks in advance for your patience.

T.

Kosmaj · 2005-02-01, 01:52

Quote:

Originally Posted by Tumo

I present to you this:
K=237, Base=2, Nmin=524288, Nmax=1048576, k.b^n-1 with fixed k.
The same 'collapse' occurs.

Can you be more specific? What do you mean by 'collapse'. Sorry, but I don't have time to try it right now.

For one possible decision of when to stop sieving check the "Expert Users" section here although, fankly speaking I don't use it. It depends on the weight of k, i.e., the survival rate, how many machines do you have, do you PRP/LLR on all machines or you have some for sieving only. Use P3's only to sieve, Athlons both to sieve and LLR and P4's only to LLR. For medium weight k's in the n=200-500k range sieving to 1E12 (1T) is enough. For larger n's to 1M sieve at least to 2T.

Also, please note that we have an informal reservation system in this thread for small k<300 where you can declare k's and the ranges of n you are currently working on. So that we don't duplicate our efforts. In case of high-weight 15k's you can just reserve one or more k's and test them as much as you want.

For more details on project currently running please read all posts in this thread and check the links mentioned there.

2005-02-01, 15:33

Quote:

"for a given K, sieving in a particular range of Nmin->Nmax, at what point do you tell a novice when to stop the sieve and simply 'bite the bullet', running PRP/LLR on all remaining N in the file (including the N that would have been removed if P were to run higher)?"

The answer for a novice windows user is,
"Use RMA's automation option."

You can do "fixed k" sieving, without the preference for
"RMA enable" checked, to sieve and test at the same time.

It's still in a beta stage, but it works ok for most.
I'm just gearing up for multi-base implementation of the algorithm.

2005-02-01, 16:09

RMA BETA 2.9 does not do that option right now.
I made some changes and forgot to update the "other options".
Soon this will be fixed...(tonight).

I should explain that:
RMA's Full Auto, follows Paul Jobling's statement:

In the Help/contents tab of Newpgen it states:
"In general, you ought to sieve until the rate at which NewPGen is
throwing out composites is equal to the rate at which Proth/PRP/PFGW/LLR
can perform a primality test on the numbers. Actually, you should stop a little sooner -
the idea is to find primes, after all."(Paul Jobling)

This is precisely what the Full Auto option does.

2005-01-31, 02:12	#1
Tumo Jan 2005 19 Posts	Possible loophole/bug in NPG 2.82 ??? Please forgive my being a novice, but i stumbled onto either a user error (which i suspect is most likely) or a possible problem with NPG (hard to believe one could exist). NPG, Dec 2004 version... try k.b^n-1 with k fixed enter b=2, k=7 nmin=2, nmax=65536 and run (with or w/o verify) @P= 2G, stop the sieve... examine the output file.. you will find something like: 2256610126:M:0:2:258 7 29 7 45 7 101 7 177 now start again, and notice the Nmin window has updated from 2 to 29. At some point above 4G (I stopped closer to 6G)... stop the sieve again. examine the output files. I find this: 6426074968:M:0:2:258 7 45 7 101 7 177 I have verified this condition on both AMD64 FX and Intel P4b (both are SSE2 machines)... both on Win/XP.. AMD on SP1, P4 on SP2. 72^29-1 is valid from everything I've seen, listed in the forums and shows up valid by LLR 3.3. Also, i believe other values lower than 29 are missing, true? I tripped over this after the recommended 24+ hours of sieving for an LLR run. I had crossed well over 250G at that point... When I ran the numbers, NOTHING came up prime. According to the period/frequency of the prime, I should have had several hits. I went to the 'Riesel < 300' page, selected a test range for others and did it again, and again... then went back to basics which brings me here. May I ask what it is I am tripping over? I am stumped. I thank you for your time and tolerance. I also thank you in advance for your assistance. Chuck Last fiddled with by Tumo on 2005-01-31 at 02:17*

2005-01-31, 10:16	#3
Keller May 2004 2²·7 Posts	But this is a serious bug and might have caused lots of problems ... For example Rieselsieve, PSP or SoB ... Maybe values of n have been missed that are smaller than n=64 and maybe they are wasting lots of work because a tiny number has been missed ... Who knows ;) Last fiddled with by Keller on 2005-01-31 at 10:17

2005-01-31, 10:52	#4
em99010pepe Sep 2004 101100001110₂ Posts	Hello, Yesterday I noticed that too. I wanted to reserve a Sierpinsksibase4k=63411 but I first run newpgen 2.82 to see the size of the outputfile. k=63411; base=4; nmin=10000, nmax=100000 The first run gave me this: 16738300:P:0:4:257 63411 10000 63411 10016 63411 10076 63411 10140 63411 10196 63411 10212 63411 10256 63411 10292 63411 10302 63411 10307 63411 10308 63411 10313 63411 10317 63411 10320 63411 10322 63411 10326 63411 10331 63411 10337 63411 10338 63411 10352 63411 10353 63411 10361 63411 10362 63411 10365 63411 10370 63411 10377 63411 10380 63411 10385 63411 10388 63411 10395 And the second one this: 36278740:P:0:4:257 63411 10016 63411 10076 63411 10140 63411 10196 63411 10212 63411 10256 63411 10292 63411 10320 63411 10400 I still have both files. Cheers, Carlos Last fiddled with by em99010pepe on 2005-01-31 at 10:54

2005-02-01, 00:56	#6
Tumo Jan 2005 19 Posts	I can understand the low value situation easily and accept that. I present to you this: K=237, Base=2, Nmin=524288, Nmax=1048576, k.b^n-1 with fixed k. The same 'collapse' occurs. Understanding that it's a recursive condition of not eliminating an N (aka K/N pair).. and then having that same N (K/N pair) be removed by a higher value P. It is easy for me to sieve up to P = 1 Tera in 24 hours or so. Given this to make perfect sense, at what 'P' value does one stop sieving? I sieve for 24 hours , as commonly recommended, and this usually puts me in the High-'G' range. Is it common and reasonable to expect that only the largest N of that sieve, regardless of P,K, or N ranges set at the start, will be left? It seems this is a recursive factorization issue and I see now that I should probably rephrase my initial question to be: "for a given K, sieving in a particular range of Nmin->Nmax, at what point do you tell a novice when to stop the sieve and simply 'bite the bullet', running PRP/LLR on all remaining N in the file (including the N that would have been removed if P were to run higher)?" Sorry if I am being thick (slow to learn) about this, I am just trying to understand the relationships that you all have had great experience with. I can sieve at a very fast speed, but my LLR time is embarassingly slow, hence my desire to remove as many N as possible and reasonable. Thanks for all the advice. Thanks in advance for your patience. T. Last fiddled with by Tumo on 2005-02-01 at 00:59

2005-02-01, 16:09	#9
TTn 2²·557 Posts	broken RMA BETA 2.9 does not do that option right now. I made some changes and forgot to update the "other options". Soon this will be fixed...(tonight). I should explain that: RMA's Full Auto, follows Paul Jobling's statement: In the Help/contents tab of Newpgen it states: "In general, you ought to sieve until the rate at which NewPGen is throwing out composites is equal to the rate at which Proth/PRP/PFGW/LLR can perform a primality test on the numbers. Actually, you should stop a little sooner - the idea is to find primes, after all."(Paul Jobling) This is precisely what the Full Auto option does. Last fiddled with by TTn on 2005-02-01 at 16:12