20081123, 02:22  #1 
May 2007
Kansas; USA
10372_{10} Posts 
Riesel base 3 new testing idea
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 krange); 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^01 = k*11 = k1 So, all that one has to do with a k that is divisible by b is to test and see if k1 is prime. If so, that k can be removed! What brought this to light here is that I thought I'd try a doublecheck on the k=500M505M 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 k1 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 kvalue must be == 2 mod 6]: ABC2 $b*3^$a1 // {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 kvalue must be == 4 mod 6]: ABC2 $b*3^$a1 // {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^$a1 // {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 kvalue instead of nvalue when doing many k's over a relatively small nrange. 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 krange, approximately 1 out of 20 numbers is prime. So instead of testing all even kvalues 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. Last fiddled with by gd_barnes on 20081123 at 02:24 
20081212, 21:30  #2  
I quite division it
"Chris"
Feb 2005
England
4035_{8} Posts 
Quote:
Quote:
Quote:
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: Quote:
Last fiddled with by Flatlander on 20081212 at 22:19 

20081214, 04:09  #3  
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
I've adapted Willem's script from the 'Starting your own base 101' thread.
I think it does what Gary suggested above. Quote:
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 k1. Last fiddled with by Flatlander on 20081214 at 04:21 

20081214, 15:56  #4  
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
Quote:
If have run this: Code:
ABC2 $a a: from 660000005 to 700000000 step 6 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%. Last fiddled with by Flatlander on 20081214 at 16:51 

20081214, 18:26  #5  
May 2007
Kansas; USA
2^{2}×2,593 Posts 
Quote:
They were only identical because you did not happen to encounter any composite 3PRP'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 3PRP's and then run another test using the tp switch only on the 3PRP's to verify primality. Gary 

20081214, 21:39  #6  
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
Here's what I'll do :
1) Run RB3start.txt with f. (Delete pfgw.log and pfgwprime.log.) 2) Run this: Quote:
Compare the two files. (fc pfgw.log pfgwprime.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 pfgwprime.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. Last fiddled with by Flatlander on 20081214 at 21:40 

20081215, 04:11  #7  
May 2007
Kansas; USA
2^{2}×2,593 Posts 
Quote:
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 

20081215, 06:13  #8 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
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.

20081215, 13:28  #9  
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
Quote:
edit: I wasn't sure if they were possible; apparently not then. Quote:
Code:
Psuedocode: FOR k = mink TO maxk STEP 2 IF k mod 6 == 0 THEN only test this k if k1 is prime ELSE Test this k NEXT k Last fiddled with by Flatlander on 20081215 at 14:26 

20081217, 03:13  #10  
May 2007
Kansas; USA
24204_{8} Posts 
Quote:
Thanks for the pseudocode. It looks correct. 

20081220, 00:19  #11 
I quite division it
"Chris"
Feb 2005
England
31·67 Posts 
This:
Code:
ABC2 $a a: from 3 to 20000001 step 2 Last fiddled with by Flatlander on 20081220 at 00:19 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Riesel/Sierp base 2 evenk/evenn/oddn testing  gd_barnes  Conjectures 'R Us  428  20210515 15:43 
Riesel base 2 discussion  gd_barnes  Conjectures 'R Us  84  20110603 18:07 
Base6 speed for prime testing vs. base2  jasong  Conjectures 'R Us  36  20100803 06:25 
Riesel Base 5 LLR  em99010pepe  Sierpinski/Riesel Base 5  8  20100608 21:21 
Sierpinski / Riesel  Base 22  michaf  Conjectures 'R Us  49  20071217 05:03 