Riesel base 3 new testing idea

[gd_barnes]

I don't want to mess up the automated scripts that are already set up but......how would everyone like to only test 43% instead of 50% of all k's (at the current k-range); hence cutting 14% off of total testing time as well as relieving Kenneth of the burden of removing multiples of the base?!!

Here's the deal:
In the automated processing thread, Karsten and I and others were having a discussion about appropriatly removing k's that are multiples of the base. After much thinking on my part, I determined that such a thing was actually quite easy. Willem (Siemelink) confirmed my thinking. It goes like this: If a k that is divisible by the base (b) has a prime at n=0, then the k must remain otherwise it can be removed immediately. That's all!

To make it a little easier, I came up with the following:
k*b^0-1 = k*1-1 = k-1

So, all that one has to do with a k that is divisible by b is to test and see if k-1 is prime. If so, that k can be removed!

What brought this to light here is that I thought I'd try a double-check on the k=500M-505M range due to the extremely few # of k's remaining. I only have 2 slow cores that I'm willing to put on it and I wanted as fast a way as possible to do it.

With that explanation out of the way, here is my idea: Since only even k must be tested for base 3 and we want to separate out k's divisible by b, we have 3 different tests we need to run:

1. all k==(2 mod 6)
2. all k==(4 mod 6)
3. all k==(0 mod 6) but only where k-1 is prime


Based on that, I came up with the following 3 PFGW scripts that need to be run:

Script 1, test all k==(2 mod 6); (starting k-value must be == 2 mod 6]:

ABC2 $b*3^$a-1 // {number_primes,$b,1}
a: from 1 to 10000
b: from 500e6 to 505e6 step 6

Script 2, test all k==(4 mod 6); [starting k-value must be == 4 mod 6]:

ABC2 $b*3^$a-1 // {number_primes,$b,1}
a: from 1 to 10000
b: from 500000002 to 505e6 step 6

Script 3, the coupe de grace :

ABC2 ($b+1)*3^$a-1 // {number_primes,$b,1}
a: from 1 to 10000
b: primes from 500e6 to 505e6
:surprised


The kicker here is that script 3 is actually testing 2 TIMES as many k's as it needs to. When it's done, if there are any k's remaining without a prime, you have to remove any of them NOT divisible by 3.

If there was a way to make PFGW only test k's where a prime+1 was divisible by 3, it would test exactly the k's needed and we could save ~30% of our total testing time.

As you can see, I like to test by k-value instead of n-value when doing many k's over a relatively small n-range. That allows me to stop it at any point since PFGW has the bad habit of not remembering the k's that it has found a prime for when you restart it.

Although I only have 2 cores for it, each core just runs 1/3rd slower.

I based my % savings on the fact that at this k-range, approximately 1 out of 20 numbers is prime. So instead of testing all even k-values or half of them, you end up testing:

1/6 + 1/6 + 1/20*2 = 5/30 + 5/30 + 3/30 = 13/30 = 43%. So percentage of time saved = 1 - 43/50 = .14 or 14%.


Gary


P.S. I'm still trying to think of a way to make PFGW not test the primes where prime+1 is divisible by 3 and still stop after finding a prime for each one. It can be done but it either wouldn't stop after a prime or it would skip some k's.

[Flatlander]

Originally Posted by gd_barnes

...
P.S. I'm still trying to think of a way to make PFGW not test the primes where prime+1 is divisible by 3 and still stop after finding a prime for each one. It can be done but it either wouldn't stop after a prime or it would skip some k's.

Any success with that?

If a k that is divisible by the base (b) has a prime at n=0, then the k must remain otherwise it can be removed immediately.

So, all that one has to do with a k that is divisible by b is to test and see if k-1 is prime. If so, that k can be removed!

Is it me or you?

Before I start the range I have just reserved maybe you could tell me what you think is the optimum/fastest way of testing a range.

edit:

a: from 1 to 10000

Why did you choose 10000?

[Flatlander]

I've adapted Willem's script from the 'Starting your own base 101' thread.
I think it does what Gary suggested above.

1. all k==(2 mod 6)
2. all k==(4 mod 6)
3. all k==(0 mod 6) but only where k-1 is prime

Chris


edit: Aaargh! It's 4:10 a.m. I should be in bed.

It might have to be run with -tp because we need primes not PRPs for k-1.

[Flatlander]

Originally Posted by Flatlander

...

It might have to be run with -tp because we need primes not PRPs for k-1.

It would seem this is not necessary.
If have run this:

ABC2 $a
a: from 660000005 to 700000000 step 6

with and without -tp, and the two files are identical. (I will test higher soon.)
I will now start my reserved range using the script above. If someone spots something wrong I will restart.

edit:
983,552 primes were produced for the 6.67m tests in the above giving a density of 14.75%.

[gd_barnes]

Originally Posted by Flatlander

It would seem this is not necessary.
If have run this:

ABC2 $a
a: from 660000005 to 700000000 step 6

with and without -tp, and the two files are identical. (I will test higher soon.)
I will now start my reserved range using the script above. If someone spots something wrong I will restart.

edit:
983,552 primes were produced for the 6.67m tests in the above giving a density of 14.75%.

They were only identical because you did not happen to encounter any composite 3-PRP's in the particular range that you tested. They are very rare, even at the low range that you are testing but they will be there eventually.

You definitely need to test with the -tp option at some point. You can run an initial test without it to get the 3-PRP's and then run another test using the -tp switch only on the 3-PRP's to verify primality.


Gary

[Flatlander]

Here's what I'll do :

1) Run RB3start.txt with -f. (Delete pfgw.log and pfgw-prime.log.)

2) Run this:

ABC2 $a
a: from 500000005 to 510000000 step 6

First with -f, then with -tp.
Compare the two files. (fc pfgw.log pfgw-prime.log >differences.txt)
Any composite PRPs (false positives) can be deleted from the file generated in step 1.
Any primes that weren't found as PRPs (false negatives) must be tested individually.
(Delete or rename pfgw.log and pfgw-prime.log before next step.)

3) Check the PRPs found in step 1 with -tp. (Check for composite PRPs and find the first real prime for those ks.)

4) Sieve/test the remaining ks from step 1, to n=25000.


Though, in fact, I have already tested ks from 660m to 1bn (step 2) and there were no false positives or false negatives. So step 2 can be skipped for now.

[gd_barnes]

Originally Posted by Flatlander

Here's what I'll do :

1) Run RB3start.txt with -f. (Delete pfgw.log and pfgw-prime.log.)

2) Run this:
First with -f, then with -tp.
Compare the two files. (fc pfgw.log pfgw-prime.log >differences.txt)
Any composite PRPs (false positives) can be deleted from the file generated in step 1.
Any primes that weren't found as PRPs (false negatives) must be tested individually.
(Delete or rename pfgw.log and pfgw-prime.log before next step.)

3) Check the PRPs found in step 1 with -tp. (Check for composite PRPs and find the first real prime for those ks.)

4) Sieve/test the remaining ks from step 1, to n=25000.


Though, in fact, I have already tested ks from 660m to 1bn (step 2) and there were no false positives or false negatives. So step 2 can be skipped for now.

This looks OK but I'll have to trust you on some of it because:

1. I'm not familiar enough with the code in RB3start.txt that you posted to properly review it.

2. I don't know what you mean by false negatives. I've never known a prime that was not a PRP. Is that possible? Assuming not, the statement about the 'false negatives' is a moot point and doesn't really matter.


Gary

[mdettweiler]

Originally Posted by gd_barnes

2. I don't know what you mean by false negatives. I've never known a prime that was not a PRP. Is that possible? Assuming not, the statement about the 'false negatives' is a moot point and doesn't really matter.

No, "false negatives" are not possible. Assuming that the machine used is reasonably stable, if a PRP test says a number is composite, it is *definitely* composite. The only doubt that PRP tests leave is in regard to the probable primes themselves.

[Flatlander]

Originally Posted by mdettweiler

No, "false negatives" are not possible. Assuming that the machine used is reasonably stable, if a PRP test says a number is composite, it is *definitely* composite. The only doubt that PRP tests leave is in regard to the probable primes themselves.

By' false negative' I meant a prime for which no PRP had been found. Any differences between the PRP file and the prime file will be easily detected.

edit:
I wasn't sure if they were possible; apparently not then.

1. I'm not familiar enough with the code in RB3start.txt that you posted to properly review it.

Basically, it's just:

Psuedocode:
FOR k = mink TO maxk STEP 2
IF  k mod 6 == 0 THEN only test this k if k-1 is prime
ELSE
Test this k
NEXT k

(My granny would turn in her grave if she saw all the GOTOs in the real code. I have programmed (mostly BASIC) on and off since 1982 but, iirc, this is the first time I have used GOTO.)

[gd_barnes]

Originally Posted by Flatlander

By' false negative' I meant a prime for which no PRP had been found. Any differences between the PRP file and the prime file will be easily detected.

edit:
I wasn't sure if they were possible; apparently not then.


Basically, it's just:

Psuedocode:
FOR k = mink TO maxk STEP 2
IF  k mod 6 == 0 THEN only test this k if k-1 is prime
ELSE
Test this k
NEXT k

(My granny would turn in her grave if she saw all the GOTOs in the real code. I have programmed (mostly BASIC) on and off since 1982 but, iirc, this is the first time I have used GOTO.)

Thanks for the pseudocode. It looks correct.

[Flatlander]

This:

ABC2 $a
a: from 3 to 20000001 step 2

produces identical results with -f and -tp, so now I know it's safe to automatically remove m.o.b. and trivial ks for other conjectures with k up to 2000001.