Software/instructions/questions

[Mini-Geek]

http://sites.google.com/site/timsorb...edirects=0&d=1
I included the newest versions of everything except NewPGen.

[gd_barnes]

Thanks a bunch Tim. I have included your link in the 1st post here. I have also removed all references to NewPGen in the 1st two posts here. NewPGen should not be used for anything at CRUS or NPLB.

[Mini-Geek]

Isn't it true that LLR is faster for power-of-2 bases and PFGW is faster for other bases? The third post makes it sound like LLR is significantly faster than PFGW for all bases. Besides, it's a lot of hassle to remove k's with primes from LLR, something PFGW can do automatically. (Perhaps you just haven't 'modernized' that post yet to consider PFGW's improvement.)

Originally Posted by gd_barnes

3. Restart LLR with the sieved file that has the eliminated k's. IMPORTANT...be sure and change the input line #. Otherwise it will start LLRing much later in the file and you'll miss searching many candidates.

I think it's easier to remove all lines before the one you're supposed to run next, then just set the line number to 1. Less room for error, too.

Originally Posted by gd_barnes

2. Change the first line of the sieved file, i.e. the "XXXXXXXX:1:P:24:257" line to "ABC $b*24^$a+1 // {number_primes,$a,1}". Do not change the $b and $a variables.

Shouldn't that be "$a*24^$b+1"? I'm pretty sure the other way around would take the k as the n and vice versa and stop processing the n when a prime is found for it (or just not work at all).

[gd_barnes]

Originally Posted by Mini-Geek

Isn't it true that LLR is faster for power-of-2 bases and PFGW is faster for other bases? The third post makes it sound like LLR is significantly faster than PFGW for all bases. Besides, it's a lot of hassle to remove k's with primes from LLR, something PFGW can do automatically. (Perhaps you just haven't 'modernized' that post yet to consider PFGW's improvement.)

I think it's easier to remove all lines before the one you're supposed to run next, then just set the line number to 1. Less room for error, too.

Shouldn't that be "$a*24^$b+1"? I'm pretty sure the other way around would take the k as the n and vice versa and stop processing the n when a prime is found for it (or just not work at all).

I only updated the 1st two posts here. I was not intending the update the 3rd post but I'll go ahead and do that after I get back from a business trip. The $a, $b does appear that I goofed originally there. I'll correct that now.

To avoid confusion, I put an editors note at the beginning of the 3rd post stating that it is now out of date.

Thanks for checking everything closely Tim. It's surprising how difficult it is to keep everything up to date at all times for two projects.

[rogue]

My recommendation for starting new bases is that you should use the PFGW script only up to 100 or 200. Take the k without primes and run them through srsieve. Sieve from where to stopped to n=1000. You just need to sieve to a few million. This will eliminate a large number of tests very quickly. Create the PFGW input file with srfile. At every hundred or so stop PFGW then use srfile to remove bases which have a prime. You will then need to edit the output from srfile to drop low n and restart PFGW. For Sierpinski base 58, this saved many hours. I estimated that the time it would have taken was about 10 hours to go to n=1000 had I used the script to go that far. Using this method, I shaved off about 90% of that time and got to n=1000 in about an hour. Granted it takes more manual effort, but it saves a lot of time in the long run.

[Siemelink]

Originally Posted by rogue

My recommendation for starting new bases is that you should use the PFGW script only up to 100 or 200. Take the k without primes and run them through srsieve. Sieve from where to stopped to n=1000. You just need to sieve to a few million. This will eliminate a large number of tests very quickly. Create the PFGW input file with srfile. At every hundred or so stop PFGW then use srfile to remove bases which have a prime. You will then need to edit the output from srfile to drop low n and restart PFGW. For Sierpinski base 58, this saved many hours. I estimated that the time it would have taken was about 10 hours to go to n=1000 had I used the script to go that far. Using this method, I shaved off about 90% of that time and got to n=1000 in about an hour. Granted it takes more manual effort, but it saves a lot of time in the long run.

I concur and raise you one!

make srsieve give output in ABC format and add // {number_primes,$a,1} to the end of the first line. That way PFGW will skip k's for you and there is no need for srfile until you exit and restart PFGW.

Willem.
ABC $a*36^$b-1 // {number_primes,$a,1}

[gd_barnes]

IMHO, that is too much manual effort. I just stick some PFGW scripts on a core or 2 for a few hours or a day or two up to n=1000 or n=2500 and let it hack away until done. Usually there are only a few 100 k's or perhaps a 1000 or 2000 k's remaining. At that point, there should be only a few k's that are multiples of the base or that have algebraic factors that would allow them to be removed, which is what generally takes the time to figure.

With what you are suggesting, you have 1000's or 10000's (or more) k's remaining at n=100 or some other low limit. You're then forced to create a huge equations file for srsieve and continue manually removing them for the several times that you sieve.

I suppose it depends on if the ratio of the following is very high:

The number of cores that you have divided by the amount of personal time that you have. (lol; funny but true)

In the case described by Mark, he's saying that it would have taken 10 CPU hours to run the script to n=1000 vs. 1 CPU hour to do what he did, which I'm assuming probably involved at least an hour of his personal time vs. 5-10 mins. to create the PFGW sripts correctly. Personally I'd choose the 10 CPU hours every time if it took an hour or more of my personal time.

Now...if you're talking 10 CPU days vs. 1 CPU day, that's a different story but for most bases, it doesn't take nearly that long to PFGW with scripts to n=1000. (I actually go to n=2500 on most bases because I don't want to mess with testing any more multiples of the base than I have to or creating huge equations files of k's remaining for srsieve.) So it's really a matter of magnitude. In most cases, PFGWing without sieving to n=1000 or n=2500 doesn't take more than 1 or 2 CPU days so that would be my choice.

That's just my two cents anyway...

BTW, I'll do some more updating on posts 2 and 3 here late this week or early next week. Someone please "bump" me if I forget.


Gary

[rogue]

Originally Posted by gd_barnes

3. When reviewing and reporting the k's remaining, eliminate multiples of the base where k-1 is composite (Riesel side) or where k+1 is composite (Sierp side). This effectively avoids running duplicate searches.

Could you explain the math behind this statement? I presume that one can derive a factorization of k*b^n+/-1 under these conditions, but I'm not seeing it right now.

[Mini-Geek]

Originally Posted by rogue

Could you explain the math behind this statement? I presume that one can derive a factorization of k*b^n+/-1 under these conditions, but I'm not seeing it right now.

(I just worked this myself, so some of the work and/or logic might not be right, but it sounds right to me, and comes to a conclusion that agrees with Gary's result)
For every k that is a multiple of the base (say the xth multiple), xb*b^n±1 = x*b^(n+1)±1
The reason is simple, but here it is worked out any way:

k=xb
xb*b^n-1=
x*b*b^n-1
We know that a^b*a^c=a^(b+c), so:
x*b^1*b^n-1=
x*b^(n+1)-1

So for every multiple of a base, there is a one-to-one mapping to a smaller k.
Now the question is: where does the primality of k-1 come in? There is indeed a one-to-one mapping as previously established, (which might suggest that if one has primes, so does the other) but we only consider n≥1, so x*b^1-1=xb*b^0-1 is ignored for determining if xb is a Riesel/Sierp number. Keep in mind that b^0=1, so xb*b^0-1=xb-1=k-1. If xb-1 is composite, then xb and x (as k's) will fall into the same category of being or not being Riesel/Sierp numbers, and we can ignore xb and continue working on the smaller x. If it is prime, then x is eliminated at n=1, but xb still remains, so they might not fall into the same category of not being Riesel/Sierp numbers, so we need to check if xb is a Riesel/Sierp number.

For some examples of how this works out see:
(105=15*7, x=7, b=15, and k-1=104 is composite)
105*15^n-1
7*15^n-1
Note that 105*15^0-1=7*15^1-1=104, 104 is composite so k=7 might be a Riesel number, and that 105*15^n-1=7*15^(n+1)-1, so every n from 105*15^1-1=7*15^2-1 up is a simple one-to-one and so if one has a prime, so will the other, so we only have to check one of the two. We decide to check k=7 and ignore k=105 because 7 is smaller.

(30=15*2, x=2, b=15, and k+1=31 is prime)
30*15^n+1
2*15^n+1
Note that 30*15^0+1=2*15^1+1=31, 31 is prime so k=2 is not a Sierp number, but 30 might still be a Sierp number, so we only have to check k=30 for primes.

So in the end, we should eliminate k's where k is a multiple of the base and k-1 is composite (Riesel side) or k+1 is composite (Sierp side), just like Gary said.

That was much easier than I thought it'd be.

[rogue]

Originally Posted by Mini-Geek

So for every multiple of a base, there is a one-to-one mapping to a smaller k.
Now the question is: where does the primality of k-1 come in? There is indeed a one-to-one mapping as previously established, (which might suggest that if one has primes, so does the other) but we only consider n≥1, so x*b^1-1=xb*b^0-1 is ignored for determining if xb is a Riesel/Sierp number. Keep in mind that b^0=1, so xb*b^0-1=xb-1=k-1. If xb-1 is composite, then xb and x (as k's) will fall into the same category of being or not being Riesel/Sierp numbers, and we can ignore xb and continue working on the smaller x. If it is prime, then x is eliminated at n=1, but xb still remains, so they might not fall into the same category of not being Riesel/Sierp numbers, so we need to check if xb is a Riesel/Sierp number.

For some examples of how this works out see:
(105=15*7, x=7, b=15, and k-1=104 is composite)
105*15^n-1
7*15^n-1
Note that 105*15^0-1=7*15^1-1=104, 104 is composite so k=7 might be a Riesel number, and that 105*15^n-1=7*15^(n+1)-1, so every n from 105*15^1-1=7*15^2-1 up is a simple one-to-one and so if one has a prime, so will the other, so we only have to check one of the two. We decide to check k=7 and ignore k=105 because 7 is smaller.

(30=15*2, x=2, b=15, and k+1=31 is prime)
30*15^n+1
2*15^n+1
Note that 30*15^0+1=2*15^1+1=31, 31 is prime so k=2 is not a Sierp number, but 30 might still be a Sierp number, so we only have to check k=30 for primes.

Barring the confusion of some of your phrases, I'm curious about something. Where in the definition of the conjecture does it say that n could be 0 if k is a multiple of b? It can't be 0 for any other k. Why the exception?

AFAIAC the above logic is confusing because the exception isn't clearly noted. With the exception I would simply state (in code) that n can start at 0 if k is a multiple of b. The rest of the code handles itself.

[Mini-Geek]

Originally Posted by rogue

Barring the confusion of some of your phrases, I'm curious about something. Where in the definition of the conjecture does it say that n could be 0 if k is a multiple of b? It can't be 0 for any other k. Why the exception?

It can't. Sorry for writing in a way that made you think that. We don't consider n=0 to be part of the set of numbers considered in determining if k is a Riesel/Sierp number, whether it's a multiple of the base or not. I was just pointing out that n=1 on x is n=0 on xb (which means this specific number is ignored for k=xb; and also pointing out that k=xb*b^0-1=x*b^1-1=k-1). Sorry for any confusion that caused.

Originally Posted by rogue

AFAIAC the above logic is confusing because the exception isn't clearly noted. With the exception I would simply state (in code) that n can start at 0 if k is a multiple of b. The rest of the code handles itself.

Sorry for confusing you on this point, but no that's not how it works. That would make xb be exactly the same as x. (except you'd be calling the numbers by a slightly different name)

To (hopefully) clarify:
k=x and k=xb are the same, except that the n's are offset from each other by 1, and k=x n=1 is k=xb n=0 (the latter of which is ignored, for purposes of Riesel/Sierp number candidacy, like any other n=0). Every number xb*b^n-1 with n≥1 is contained within x*b^n-1 with n≥1. x*b^1-1 is not within xb*b^n-1 with n≥1 (as it's at n=0). Therefore x*b^1-1 (which is also xb*b^0-1, xb-1, and k-1 when k=xb) is integral to the relationship of x and xb and which one should be tested for further primes.
(for a visual example of this, look at the first few numbers for the examples I gave and see that e.g. every 105*15^n-1 number is on 7*15^n-1, but k=7 has 104 as one of the values while k=105 does not)

If x*b^1-1, (which is also k-1 when k=xb, which is where we get the k-1 notation) is composite, then k=x and k=xb still remain as possible Riesel numbers. Since from this point on there is no significant difference between the two, we choose to ignore the larger one, k=xb (the same work will be done with k=x).
i.e. we remove k's that are multiple of the base when k-1 is composite.

If x*b^1-1 is prime, then k=x is eliminated as a Riesel candidate, but k=xb still needs to be checked (although k-1 is of the form xb*b^n-1, it is with n=0 so we don't consider it as a prime that eliminates xb as a Riesel number).
i.e. we keep k's that are multiple of the base when k-1 is prime.