Riesel base 3 composite PRPs

[Flatlander]

Fellow crunchers,

Despite running PFGW with -f I am still getting composite PRPs.
If I try to load the PRP and prime files for n<=1000 into Winmerge it runs out of memory when getting to 1.35GB. (I have 2 GB. I have also tried WinDiff.)
It is possible to split the files into parts just using WordPad but it grinds to a halt for a couple of minutes everytime I try to scroll etc.

In other words, identifying the composite PRPs in large files is too much of a pain for me.

The options for me are:

a) I just report that composite PRPs exist for a certain range.
b) I email the PRP and prime files to someone so they can find the little, er, offenders.
c) I run PFGW with -f1000 or something, wasting some time. (I don't mind doing this.)
d) Someone comes up with a nice solution that I am overlooking.


Regards,
Chris

Just found the DOS command 'fc'.
(I had tried 'Comp' which just said that the files were different. I didn't know there was another comparison command.)

Now I can just run a .bat file. What's a command for not closing the dos box so I can copy and mark the output?
Or even better, sending the output to a file "checkme.txt".

[KEP]

Flatlander, the easiest is to just don't care about the PRPs being composites, since eventually while the proof is constructed, they will be found. In fact I think (please correct me if I'm wrong) that it is not important to verify the PRP with n<=1000 since these primes is not desired by Gary at the moment. Also any composites primes for n<=1000 will most likely have a n for n<=25000, which makes the k*3^n-1 a prime

Regards

Kenneth

Admin edit: Yes we do care about PRPs being composites! After running an intial test to get PRP's, please run a second test with the -tp switch to prove them. Thanks.

[henryzz]

use textpad
open both files in it at once
then click tools --> compare files

[kar_bon]

Originally Posted by Flatlander

Just found the DOS command 'fc'.
(I had tried 'Comp' which just said that the files were different. I didn't know there was another comparison command.)

Now I can just run a .bat file. What's a command for not closing the dos box so I can copy and mark the output?
Or even better, sending the output to a file "checkme.txt".

put the last line 'pause' in your bat-file and the dos-box will still open until pressing a key.

and you can call your command like 'fc 1.txt 2.txt >output.txt' to redirect the output to a file.

i can offer you a gawk-script to collect/split rows from a pfgw-res-file; i did this because every text-editor is unable to handle big files (say 1.5GB, got those for some testings with pfgw!) in a proper time!
tell me what you need to do, example is useful.

[masser]

Originally Posted by Flatlander

Fellow crunchers,

Despite running PFGW with -f I am still getting composite PRPs.

a) I just report that composite PRPs exist for a certain range.
b) I email the PRP and prime files to someone so they can find the little, er, offenders.
c) I run PFGW with -f1000 or something, wasting some time. (I don't mind doing this.)
d) Someone comes up with a nice solution that I am overlooking.


Regards,
Chris

pfgw -f will not prevent composite PRPs! There are other switches in pfgw that will allow you to do an actual primality test. IIRC, the command is something like "pfgw -t" "pfgw -tc" OR "pfgw -tm" .... RTFM!

Yes, doing actual tests takes a little longer than prp tests, but when you are doing huge amounts of small tests (it sounds like this is what you are doing) this saves you the trouble of looking for composite prps.

[Flatlander]

Originally Posted by masser

pfgw -f will not prevent composite PRPs! There are other switches in pfgw that will allow you to do an actual primality test. IIRC, the command is something like "pfgw -t" "pfgw -tc" OR "pfgw -tm" .... RTFM!

Yes, doing actual tests takes a little longer than prp tests, but when you are doing huge amounts of small tests (it sounds like this is what you are doing) this saves you the trouble of looking for composite prps.

Running prime tests (-tp) instead of PRP tests takes about 3 times as long. I was looking for a way to reduce the composite prps to the point that they effectively disappear (for the numbers we are testing) without vastly increasing the time spent.

Anyway, with the 'fc prps.txt primes.txt >difference.txt' command, the problem of finding the composite primes in the huge files produced here is effectively removed.

[gd_barnes]

Originally Posted by KEP

Flatlander, the easiest is to just don't care about the PRPs being composites, since eventually while the proof is constructed, they will be found. In fact I think (please correct me if I'm wrong) that it is not important to verify the PRP with n<=1000 since these primes is not desired by Gary at the moment. Also any composites primes for n<=1000 will most likely have a n for n<=25000, which makes the k*3^n-1 a prime

Regards

Kenneth

No way!

You are correct that I don't want the primes for n<1000 but I do care that ALL k's have primes found. You can't just leave unproven PRP's and assume that they will eventually be found when the proof is constructed. All that I'll be doing in constructing the proof is listing a prime for every k like what Masser has done for base 5. I'm not going to check them all! That is up to you guys.

I don't quite understand this thread yet with Chris saying something about a DOS compare command taking care of the problem. I'll comment further when I understand it a little better.


Gary

[gd_barnes]

I think I understand what is going on now so let me be specific:

1. You will run your standard PFGW script looking for a prime on all even k's up to some set n-limit with the -f100 switch without doing any proving. That will give you a pfgw.log file of PRP's and pfgw-prime.log file of actual primes.

2. You will run another PFGW script with the -tp switch using as input the pfgw.log file of PRP's in #1. This will give you file pfgw-prime.log of actual primes.

3. You will use some tool (doesn't matter what) to compare the pfgw.log file in #1 and the pfgw-prime.log file in #2 to find the PRP's in #1 that are not shown as prime in #2; hence they are composites.

4. You will run another PFGW script to find the primes for the composites.


That is the fastest way that I know of to get rid of the PRP's. Although it is a hassle, like you said, to run the entire range using a primality proof using the -tp switch takes FAR longer. It's easier to use that switch on tests where you know there is a 99.9+% chance of the # being prime.

When I did this, I only ran in k=1M ranges; k=10M at a time. I was able to do the above without a comparison by using the -l switch in #2, which caused it to write a results file. I then did a find on "composite" and quickly got the composite PRP's. The only problem with that is that if you did it for a huge k-range, such as k=25M or 50M at a time, you would have about the same problem as before when you tried to browse the results file looking for the word "composite". So for a huge k-range, the above method is probably best.

I have a wild idea for you though and I've done this with HUGE results files before that exceeded 100 MB. Do what I did by using the -l switch in #2 to create a results file that tells whether your PRP's are prime or composite. Then, open it up in Notepad and walk away for 5-20 mins., depending on how big the file is. (I've done this with files > 350 MB, although had to wait > 20 mins.!!)

Notepad is totally different than Wordpad in that for the file to come up at all, it has to have the entire file loaded into memory. But the good part is that when it DOES come up, there is no hesitation when you navigate or do finds on the file. Now...when you come back since it is all loaded into memory, you can do a find on "composite" and it'll go right to the first occurrence. It may take it a few secs. but once it's there, you can move up and down with ease. Now just keep doing a find on "composite" until it finds no more.

To do this, you definitely want 2 GB of memory although I've been able to do it on a 150 MB file with just 1 GB of memory while 2 instances of LLR ran in the background. You just don't want to do anything memory intensive.

It sounds archaic and basic but if you don't mind walking away or doing something else in the mean time, it's quite effective and may actually be a little faster unless you have an automated script set up to tell you what your differences are.


Gary

[Flatlander]

My eyes glazed over reading that lot!
Here's what I'm doing (Original instructions from Kenneth tweaked by me so I don't keep getting file names mixed up):

1) Run a script "start.pl" in WinPFGW.
It does a PRP test for all the ks up to N=1000. (Finds just the first prime for each k.)
It produces a file of PRPs and a file of ks that it couldn't find PRPs for.
(And two other files which are deleted.)
2) Run a -tp test on the PRPs.
3) Run "fc prps.txt primes.txt >difference.txt" to look for composite PRPs and manually find real primes for each one.
3) Sieve the ks that have no prime n<1001. (From step 1.)
4) Change the sieved file to the correct format with srfile and edit the first line to say "ABC $a*3^$b-1 // {number_primes,$a,1}". (To find the first PRP for each k.)
5) Run a -tp check on the PRPs and act on any composite PRPs as above.

The only minor 'problem' I'm having now is opening the huge sieved file to edit the first line to say "ABC $a*3^$b-1 // {number_primes,$a,1}".
Like you said, open the file and make tea/coffee. (Depending on which side of the Atlantic you are on.)

I'm still learning, but a 10M range should take just 3-4 days on one core when I've streamlined things a bit. (Though I'll probably work with 25M ranges per core to get a more efficient sieve and to save hassle.)


Footnote:
In fact, (using PFGW instead of WinPFGW) if someone can come up with a way of editing the the first line of a huge text file from a script (unfortunately, the two first lines are different lengths) I think the whole process could be done just by clicking a .bat file and coming back days later to two prime files and two files identifying any composite PRPs.

But where's the fun in that?

My goodness; look at the length of this post! I've been listening to Gary for too long!

[gd_barnes]

Originally Posted by Flatlander

My eyes glazed over reading that lot!
Here's what I'm doing (Original instructions from Kenneth tweaked by me so I don't keep getting file names mixed up):

1) Run a script "start.pl" in WinPFGW.
It does a PRP test for all the ks up to N=1000. (Finds just the first prime for each k.)
It produces a file of PRPs and a file of ks that it couldn't find PRPs for.
(And two other files which are deleted.)
2) Run a -tp test on the PRPs.
3) Run "fc prps.txt primes.txt >difference.txt" to look for composite PRPs and find real primes for each one.
3) Sieve the ks that have no prime n<1001. (From step 1.)
4) Change the sieved file to the correct format with srfile and edit the first line to say "ABC $a*3^$b-1 // {number_primes,$a,1}". (To find the first PRP for each k.)
5) Run a -tp check on the PRPs and act on any composite PRPs as above.

The only minor 'problem' I'm having now is opening the huge sieved file to edit the first line to say "ABC $a*3^$b-1 // {number_primes,$a,1}".
Like you said, open the file and make tea/coffee. (Depending on which side of the Atlantic you are on.)

I'm still learning but a 10M range should take just 3-4 days on one core when I've streamlined things a bit. (Though I'll probably work with 25M ranges per core to get a more efficient sieve and to save hassle.)

This sounds great! Nice work by Kenneth setting up the script to output k's remaining. That helps a lot!

One thing: Is it really necessary to stop PFGW at n=1000? IMHO working with such huge sieved files is a major annoyance. Couldn't you take it to n=2500 or 5000 with only a little loss of CPU time and then sieve k's remaining at that point?

Just my two cents anyway.

Edit: You left out a step: In between 4 and 5, you have to test your sieved file! lol I assume you use PFGW for that also?

I have a question, I didn't know there were 2 different versions of PFGW. I only run WinPFGW. Is the PFGW that you're referring to for Linux? I haven't run it on any of my Linux machines yet.


Gary

[Flatlander]

Originally Posted by gd_barnes

This sounds great! Nice work by Kenneth setting up the script to output k's remaining. That helps a lot!

One thing: Is it really necessary to stop PFGW at n=1000? IMHO working with such huge sieved files is a major annoyance. Couldn't you take it to n=2500 or 5000 with only a little loss of CPU time and then sieve k's remaining at that point?

Just my two cents anyway.

Edit: You left out a step: In between 4 and 5, you have to test your sieved file! lol I assume you use PFGW for that also?

I have a question, I didn't know there were 2 different versions of PFGW. I only run WinPFGW. Is the PFGW that you're referring to for Linux? I haven't run it on any of my Linux machines yet.


Gary

Er, step 4.5) was implied.
When I downloaded WinPFGW there was a WinPFGW.exe file and a PFGW.exe file in the folder. (For Windows.)

I could take the first step higher than n=1000 but then I would need to dig out primes n>1000 from a huge prime file to give to you!