Automated testing for all bases and k/n

[Siemelink]

Originally Posted by Siemelink

How about this as an easy filter:
any k can be written as 3^a*b, with a >= 0 and b not divisible by 3.
1) if there is no 0 < n <= a with b*3^n is prime you do not have to test this k.
2) if not 1) then test this k.

You can do this because we are working our way up so when b < k we can assume that b has already been tested. As we do not accept k*3^n-1 with negative n we have to exclude those with the small loop in 1)

This method will have some doubles but then there is no need to keep everything as reference.

Cheers, Willem.

Ok, I've tested a range with this now. This trick really is a timesaver, it cuts outs 33% of the tests.
I've taken the range 63063000000 until 63064644938. I ran it through the regular script until n = 5000.
This left me with 79k remaining. Of these 79, 24 are divisble by 3. Of these 24, only 1 had a prime with a low n. So the other 23 can be eliminated.

Here is an example: 63063682386*3^n-1 has no prime with n < 5000. 21021227462*3^1-1 is not a prime. 21021227462 is not divisible by 3. So there is no need to test 63063682386 because the 21021227462 will provide the prime: 21021227462*3^36742-1 = 63063682386*3^36741-1 = prime.

And the other example: 21021268414*3^1-1 is prime, we do not accept 63063805242*3^0-1 so this k has to tested in further.

This is exactly the sme what we do with other bases as well. I am just pointing out the way to do the elimination automatically.

Cheers, Willem.

[michaf]

I still have 59907 k's remaining in a 1M range, tested upto n=1k now...
I think there is a factor of 100 wrong here someplace... I reckon I should have some 600 left now! (I tested 500-501M)

Where is the catch? What do I miss? It can't be that the MOB's will delete 99% of those?

[gd_barnes]

Originally Posted by Siemelink

Ok, I've tested a range with this now. This trick really is a timesaver, it cuts outs 33% of the tests.
I've taken the range 63063000000 until 63064644938. I ran it through the regular script until n = 5000.
This left me with 79k remaining. Of these 79, 24 are divisble by 3. Of these 24, only 1 had a prime with a low n. So the other 23 can be eliminated.

Here is an example: 63063682386*3^n-1 has no prime with n < 5000. 21021227462*3^1-1 is not a prime. 21021227462 is not divisible by 3. So there is no need to test 63063682386 because the 21021227462 will provide the prime: 21021227462*3^36742-1 = 63063682386*3^36741-1 = prime.

And the other example: 21021268414*3^1-1 is prime, we do not accept 63063805242*3^0-1 so this k has to tested in further.

This is exactly the sme what we do with other bases as well. I am just pointing out the way to do the elimination automatically.

Cheers, Willem.

This is essentially what I had been stating before we came to this thread but then I attempted to over-simply things. Karsten, I'm afraid I made a mistake earlier. It's not as simple as looking to see if k/3^q remains.

Let me see if I can come up with some pseudo-code or detailed instructions for this. Unless we can get step-by-step instructions on properly removing k's that are divisible by 3, the process will not work correctly.

For now everyone, please don't use anything in Karsten's process related to removing k's that are multiples of the base. I think he already said that but I just want to make sure. k's that are multiples of the base still need to be looked at manually until we get some proper detailed specifications set up for coding it so that it can be done automatically.


Gary

[kar_bon]

Originally Posted by gd_barnes

For now everyone, please don't use anything in Karsten's process related to removing k's that are multiples of the base. I think he already said that but I just want to make sure. k's that are multiples of the base still need to be looked at manually until we get some proper detailed specifications set up for coding it so that it can be done automatically.

yes, as i wrote the 'modular'-script should not used for this purpose.
you can use this further to delete regular mods as mentioned.

i try to implement a method to delete (or perhaps make a note in a file for the user to look for) this weekend. see how far it gets.

[gd_barnes]

Originally Posted by kar_bon

yes, as i wrote the 'modular'-script should not used for this purpose.
you can use this further to delete regular mods as mentioned.

i try to implement a method to delete (or perhaps make a note in a file for the user to look for) this weekend. see how far it gets.

Oh my word...a light bulb just came on! This is SIMPLE!!

I'll make this non-base specific because this should apply to all bases; all files; etc.

It may be a little tricky for you to implement because it requires that you test each remaining k that is divisible by the base (b) for a prime at n=0.

You don't need any fancy k's remaining files or primes files or anything. You only need the k's remaining in your current process and it should be tested to n>=100.
[ Editor note: Technically it needs to be tested to > log (conjecture) / log (base), that is n=23 for Riesel base 3, but I'll keep it simple. lol ]

Here is the pseudo-code:

Read current file of k's remaining
do until end of file
  divide k by b with remainder r
  if r = 0
    run prime proof on k - 1 (or k + 1 for Sierp)
    if k - 1 (or k + 1) is prime
      keep k
    else
      discard k
    endif
  endif
  Read current file of k's remaining
enddo

What I was fighting all along is trying to avoid people testing a k where k/b^q results in a k with a very large prime found; hence causing large amounts of extra CPU time but this completely bypasses that problem!

As an explanation of checking for a prime on k-1 for Riesel or k+1 for Sierp, it is the equivalent of checking for a prime at n=0 for any base, i.e.
k*b^0-1 or k*b^0+1, which reduces to k*1-1 or k*1+1, or simply k-1 or k+1.

The beauty of the above is that if a k that is divisible by b has a prime at n=0, then any k/b^q (where q>=1) would have had a prime at n=1, n=2, etc. (i.e. some very small prime) and hence wouldn't have a large prime in the first place!

Now, if k/3^q DOES result in one where a large prime was previously found (or for that matter still remains), your current k will be discarded because if it doesn't have a prime at n=0 (which means that k/3^q doesn't have a small prime since you've tested to n=100), it goes bye-bye!

So in laymen's terms for everyone, here is what you do manually until Karsten is able to automate it:

1. Test all of your k's up to n>=100.
2. Find all of the k's remaining in your file that are divisible by the base (b).
3. Check all of those k's for primes at n=0 [or more simply check all k-1 (Riesel) or k+1 (Sierp)] for primes.
4. Keep the k's that have a prime at n=0 and discard the k's that don't.

Don't worry that you are discarding k's where a prime hasn't been found yet, even if k/b^q hasn't been tested yet, eventually it will be tested. When it is, a prime will be found that can, in effect, be converted to the k that you discarded -or- k/b^q will remain until it does have a prime, at which point you'll have the prime you need for your k that you discarded.

So there you have it! A one-stop shop for properly eliminating multiples of any base!

Gad...I have a load off my mind as this had been on my task list for several weeks because of the confusion that it has created on many bases, but especially base 3.

Regardless, math is fun!


Gary

[michaf]

Originally Posted by michaf

I still have 59907 k's remaining in a 1M range, tested upto n=1k now...
I think there is a factor of 100 wrong here someplace... I reckon I should have some 600 left now! (I tested 500-501M)

Where is the catch? What do I miss? It can't be that the MOB's will delete 99% of those?

Indeed, I had an old version of the script ... all's solved and fine

[Siemelink]

Aloha,

I've done some tinkering with my script. I tried to eliminate the k's that have the base as a factor. I reached the conclusion that these rules are sufficient.
Consider a k:

1) Assume that all smaller k's have been eliminated
2) when k % base != 0 then you have to test for primes
3) when k % base == 0 and (k-1) is a prime you have to test for primes
4) when k % base == 0 and (k-1) is not a prime you do not have to test

No need for a loop. Only one PRP test is needed to consider elimination for those k divisible by the base.

Comments please, Willem.

[michaf]

Ehm... is there a difference from your algorithm and the one from Gary?

[Siemelink]

Originally Posted by michaf

Ehm... is there a difference from your algorithm and the one from Gary?

Ah, there isn't conceptually. But I got lost in what Gary wrote the first time around.

Cheers, Willem.

[gd_barnes]

Originally Posted by Siemelink

Aloha,

I've done some tinkering with my script. I tried to eliminate the k's that have the base as a factor. I reached the conclusion that these rules are sufficient.
Consider a k:

1) Assume that all smaller k's have been eliminated
2) when k % base != 0 then you have to test for primes
3) when k % base == 0 and (k-1) is a prime you have to test for primes
4) when k % base == 0 and (k-1) is not a prime you do not have to test

No need for a loop. Only one PRP test is needed to consider elimination for those k divisible by the base.

Comments please, Willem.

Actually, I'm lost in yours. lol What does "%" and "!" mean in here?

You need a loop to read through the file! Are you just going to read one k? lol

Edit: Never mind. I figured it out. Can I put it in laymen's terms please because "%" and "!" mean little to a non-programmer?:

1) Assume that all smaller k's have been eliminated
2) when k mod base is not == 0 then you have to test for primes
3) when k mod base == 0 and (k-1) is a prime you have to test for primes
4) when k mod base == 0 and (k-1) is not a prime you do not have to test


BTW, this only works for the Riesel side. The last 2 above would need to be k+1 for the Sierpinski side.

So there you have it Karsten...verification that what I stated works in "programmer's" and "laymen's" terms.


Gary

[kar_bon]

i haven't any time to implement this easy way to delete some more k's not needed in processing. but this algorythm is quite doable without any higher software in need (pfgw and gawk do it too).

Summary:

to keep clear there are now 2 sorts of scripts for an easy way to check high ranges for any base:

1. www.rieselprime.org/dl/Automated_low_n.zip for any Riesel Base for n=1 to about 1000 (just call it Auto_Low)

2. www.rieselprime.org/dl/AutomatedLLR.zip for any Riesel Base for a sieved file of remaining k's left upto higher n (just call it Auto_LLR)

please refer to these terms.

i've just updated Auto_Low because there was an error in 'run.bat':
after halting the process during pfgw-running, you could not restart the test because the result-file was overwritten with the new results.
(technote: the fileredirection in the batch-line was edited from 'pfgw -f b%1_n%2.txt >b%1_n%2_res.txt' to 'pfgw -f b%1_n%2.txt >> b%1_n%2_res.txt')

next things to come:

- implement the described pseudocode to eliminate more k's divisible by base

- the missing link: after running Auto_Low, create a file with remaining k's, sieve it and call Auto_LLR!

Karsten