Software/instructions/questions

[gd_barnes]

This thread is for software downloads and instructions as well as a forum for any related questions on how to run software related to the No Prime Left Behind (NPLB) project.

Here is a link to all of the latest software that should be needed: http://www.noprimeleftbehind.net/crus/primebehindprogs.zip. The programs are LLR, NewPGen, Sr1sieve, Sr2sieve, Srfile, and Srsieve.

First an important note: For all of the team drives in this project, all you will need is the LLR program. Sieved files will already be provided for most searches. You will only need NewPGen and the Sr(n)sieve series of programs if you wish to do sieving yourself.

If you are an experienced prime searcher, you can most likely ignore this page. The searches with this project should be very straightforward.

Preliminaries:
I would suggest creating a separate directory for most of the programs except Srfile and NewPGen. The Sr(n)sieve series of sieving programs have a tendency to use some of the same generic file names and you don't want one sieve overlaying a prior one. Srfile could be copied into each of the 3 directories of the Sr(n)sieve programs. It is used to manipulate files of different types. NewPGen could be put anywhere. I just put it in the same directory as my LLR program.

Program instructions:
LLR - Double click on the green file icon, choose 'Test Input', key in your sieved file name, the name of the file that you would like it to write primes to, and line 1, and press OK. Primes will be in the file you specified and it will write an 'lresults.txt' file that shows details about the search.

- If you plan to do no sieving with the project, then you need not read any further. -

NewPGen - This is a sieving program that eliminates many candidates before running primality tests for only a single sequence (k-value). Sieving programs do not find primes. They only remove many candidates with small factors, which saves much time in the long run. I don't suggest using this program for this effort because it is slower than the sr(n)sieve programs and can only run one k at a time. But it does have a nice GUI interface unlike the sr(n)sieve programs, which makes it easier to run than the others that must be run at the command prompt. Many newer searchers prefer it.

To run it, double click on it, fill in the blanks on the screen, go to 'Options' 'Sieve until', key in "P=" limit to search until (probably somewhere between P=10G and 5T for most searches here) and hit OK. If you don't know how to calculate the best sieve depth, let me know and I'll help you.

Srsieve: This is an all-purpose sieving program that is used as a 'set up' for sr1sieve and sr2sieve as well as sieving very large #'s of k's more quickly than anything else. It also is very effective at sieving starting from n=1 because it does not erroneously remove low n-values that would make the equation prime. First you need to create an input file of actual equations such as 7*30^n-1, 9*30^n-1, etc., one per line. Then go to the command prompt and use the equations file as input with a command like "srsieve -a -n 25e3 -N 100e3 -P 1e9 -m 4e9 (input file). -a is the type of output file (ABC file-type in this case) -n is the low n-value of your range, -N is the high of the range, -P is how far to search (1 billion in this case), and -m tells it to not display factors on the screen less than 4G. (Unfortunately you can't set it higher than that but in this case you're not going higher so it keeps it moving by not displaying info. on the screen.

sr1sieve: This is the best program to use to sieve one k-value and is far faster than anything else for that purpose. You do need to use srsieve to sieve up to at least the value of k or the base first but I think the creator recommends something greater than P=1G. When running srsieve first, be sure and use the -g paramater to create a NewPgen-style sieved file. I personally sieve to P=250M or 500M and then let sr1sieve have at it. To run sr1sieve, go to the command prompt and try something like "sr1sieve -P 500e6 -i (input file) -o (output file). See the instructions for additional details.

sr2sieve: This one is a little tricky but it is by far the fastest for multi-k sieving anywhere from 3 k's up to probably ~100 of them. (> ~100, I think srsieve is faster). You'll want to try both. I will just tell you the steps and not how to do them:

(1) Use srsieve to sieve up to about P=1G. Force it to create an 'ABC' output file using the -a paramater.

(2) Run sr2sieve using the file in (1) as input. You'll need to specify a -P paramater that tells it how far to sieve. It knows by a value in the input file the minimum p-value to start sieving at. The command might be something like "sr2sieve -P 500e9 -i (ABC-input file). Sr2sieve will not remove prime-search candidates, it will only write factors into a file called factors.txt so one more step is needed.

(3) Run srfile with the commnd "srfile -G -k factors.txt (ABC-input file from #1). This will cause it to remove all factors found by #2 and write out a file sorted by n that LLR can do primality tests on. You're now ready to do primality tests on it.


Any questions...just ask. There is a lot of info. in the various README and other help and doc files for the programs, especially for the sr(n)sieve programs.


Gary

[TimSorbet]

(quote from "Report all primes here", but I have other questions, so I figured I'd ask all here)

Originally Posted by gd_barnes

Step 1: For people who have not submitted top-5000 primes previously, create a prover account:

...

Step 2: Create a proof code:

...

Step 3: Submit the prime:

...

Am I correct in assuming that Step 3 is the only step you'll need to do for primes after your first prime?
I'm going to be joining this project in a month (a month because that's when my next GIMPS number will finish and open up a core). I've been following it closely since it recently began.

Also, I'm wondering why there's two drives. One that's 260K-320K & 320K-333.2K and another that's 333.2K-600K. What's the significance of those different dividers? Why aren't they all in one drive? (other than that the 333.2K-600K began first) Why is the second drive 260K-320K & 320K-333.2K instead of being called 260K - 333.2K?
What program can generate the exact, full number of a k*2^n-1? Also, how (besides generating it and looking there) can you tell the exact number of digits in a k*2^n-1? I know a rough approximation would be n*log(2) because it's similar to a Mersenne number, but I don't know how to get it exactly.

[em99010pepe]

I have to agree with you. It's a nonsense having two mini-drives, better to join both...

You can generate the full number with PARI software, in here.

Exact number of digits of k*2^n-1 will be log(k)+n*log(2)-log(1).

[gd_barnes]

Originally Posted by em99010pepe

I have to agree with you. It's a nonsense having two mini-drives, better to join both...

You can generate the full number with PARI software, in here.

Exact number of digits of k*2^n-1 will be log(k)+n*log(2)-log(1).

log(1)=0 so that can be ignored. Also, you need to add 1 to obtain the # of digits after you're done and of course take the integer portion of it. The actual formula if you wanted to plug it into Excel is:

int (n*log(2)+log(k)+1)


Gary

[kar_bon]

first: 333k to 600k: to find in first place Top500 primes. every prime to check in the Top5000-list must have at least 100354 digits or n>=~333400.

second: 260k-320k: all other n tested resulting small primes not for Top5000. all k's have been tested till n=260k so this is the start range of all (including some double checks).

third: 320k-333k: in PrimeSearch to report a range done is set to 20k so there are all possible ranges upto 320k before and this last range is necessary to report 320k to 340k.

ok?

look also here: http://primes.utm.edu/top20/trends.php

[gd_barnes]

Originally Posted by Mini-Geek

(quote from "Report all primes here", but I have other questions, so I figured I'd ask all here)
Am I correct in assuming that Step 3 is the only step you'll need to do for primes after your first prime?
I'm going to be joining this project in a month (a month because that's when my next GIMPS number will finish and open up a core). I've been following it closely since it recently began.

Also, I'm wondering why there's two drives. One that's 260K-320K & 320K-333.2K and another that's 333.2K-600K. What's the significance of those different dividers? Why aren't they all in one drive? (other than that the 333.2K-600K began first) Why is the second drive 260K-320K & 320K-333.2K instead of being called 260K - 333.2K?
What program can generate the exact, full number of a k*2^n-1? Also, how (besides generating it and looking there) can you tell the exact number of digits in a k*2^n-1? I know a rough approximation would be n*log(2) because it's similar to a Mersenne number, but I don't know how to get it exactly.

You are correct, #3 is all you would need to do.

See an explanation in drive #2 as to why we specifically divided up the smaller ranges of n=260K-320K and n=320K-333.2K. It comes down to the fact that the 320K-333.2K range fills in Michael Hartley's Prime Search site reservation range of n=320K-340K for each k-value.

As for why we made them two drives; that was done because the project is potentially so huge as it is and I wanted to divide it up into top-5000 parts and non-top-5000 parts. But I'm flexible and that is a good question so...

What do others think about making it one big drive?

It would just be one long page with different sections of files to search.

Any other suggestions are welcome also.


Gary

[TimSorbet]

Originally Posted by em99010pepe

I have to agree with you. It's a nonsense having two mini-drives, better to join both...

You can generate the full number with PARI software, in here.

Exact number of digits of k*2^n-1 will be log(k)+n*log(2)-log(1).

Thanks. What does PARI use as a decimal logarithm command, if there is one?

Originally Posted by gd_barnes

log(1)=0 so that can be ignored. Also, you need to add 1 to obtain the # of digits after you're done and of course take the integer portion of it. The actual formula if you wanted to plug it into Excel is:

int (n*log(2)+log(k)+1)


Gary

Thanks for the correction to the formula.

Originally Posted by kar_bon

first: 333k to 600k: to find in first place Top500 primes. every prime to check in the Top5000-list must have at least 100354 digits or n>=~333400.

second: 260k-320k: all other n tested resulting small primes not for Top5000. all k's have been tested till n=260k so this is the start range of all (including some double checks).

third: 320k-333k: in PrimeSearch to report a range done is set to 20k so there are all possible ranges upto 320k before and this last range is necessary to report 320k to 340k.

ok?

Ok, now it makes sense.

Originally Posted by gd_barnes

You are correct, #3 is all you would need to do.

See an explanation in drive #2 as to why we specifically divided up the smaller ranges of n=260K-320K and n=320K-333.2K. It comes down to the fact that the 320K-333.2K range fills in Michael Hartley's Prime Search site reservation range of n=320K-340K for each k-value.

As for why we made them two drives; that was done because the project is potentially so huge as it is and I wanted to divide it up into top-5000 parts and non-top-5000 parts. But I'm flexible and that is a good question so...

What do others think about making it one big drive?

It would just be one long page with different sections of files to search.

Any other suggestions are welcome also.


Gary

Now that I see the differences, I'm fine with them being two drives.

This is one of the faster threads on this forum since I posted...but I think that one about LLRNet that got 35 posts in 2 hours was faster. BTW how does the LLR test work (it stands for Lucas Lehmer Riesel, right? obviously some connection to a normal LL test, but what)?

[kar_bon]

see http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers

[TimSorbet]

Originally Posted by kar_bon

see http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers

Maybe I'm missing something obvious, but I know how the LL test works for 2^p-1. What I don't know is how it works for k*2^n-1.

[kar_bon]

i found this for the moment:

http://links.jstor.org/sici?sici=002...2-F&size=LARGE

"Lucasian Criteria for the Primality of N=h*2^n-1" Mathematics of Computation, Vol. 23 108, pp. 869-875, Oct. 1969

as i know Riesel advanced the LL-Test for any number N with h>1 and proved that the starting parameter for the sequence can found to fit the test for every h.
(if my memory is right)

only this http://nl.wikipedia.org/wiki/Lucas-Lehmer-Rieseltest but netherlands!

found this:

The main theoretical fact is contained in the Theorem 5 (Lucas'Criteria for h*2^n-1) : Suppose that n=2, h is odd
A =( (a+b*sqrt(D))^2)/r, Jacobi(D,N) = -1, and Jacobi(r,N)*sign(a^2-b^2*D) = -1.
Then, a necessary and sufficient condition that N shall be prime is that u(n-2) == 0 (mod. N) 
if u(n) = u^2(n-1) - 2 with u(0) = A^h + A^-h. How to use that ?
The number u(0) can be computed using a well known recursion formula:
v(0) = 2, v(1) = A+A^-1, v(k) = v(1)*v(k-1) - v(k-2).
So, we obtain u(0) = v(h). The remaining problem is to found a value for v(1) .
The numbers A and A^-1 are units of the quadratic field K(sqrt(D))(that is to say units of the ring of the integers of this
field...). So, they are powers of the fundamental unit of the field. Instead of choosing a square free integer D and
searching for units satisfying the conditions of theorem 5, Riesel takes increasing values for v(1), and, remarking that A
and A^-1 are the roots of the equation : 
A^2 - v(1)*A + 1 = 0 computes D as the square free part of v^2(1) - 4.
It remains to verify that the resulting D, a, b and r values satisfy the conditions of theorem 5. 
The value of v(1) so found is the smallest possible.
Regards,
Jean Penné

[TimSorbet]

Originally Posted by kar_bon

only this http://nl.wikipedia.org/wiki/Lucas-Lehmer-Rieseltest but netherlands!

From the Google translation of this I was able to understand all except the instructions of what starting number to use (i.e. it's just like an LL test, but with different starting number).

Als k gelijk is aan 1, dan is 4 een goede startwaarde als n oneven is, en als n = 3 mod 4, dan geldt u 0 = 3 .
If k is equal to 1, then 4 is a good starting point when n is odd, and when n = 3 mod 4, then u 0 = 3.

Okay, I know that if k=1 it's a Mersenne and 4 is used as a starting point. After that, I don't understand the rest.

Als k = 3, dan moet u 0 gelijk zijn aan 5778 voor n = 0 of 3 mod 4.
When k = 3, then u 0 must equal 5778 for n = 0 or 3 mod 4.

Als geldt dat k = 1 of 5 mod 6 en 3 deelt N niet, dan geldt .
If true that k = 1 or 5 mod 6 and 3 shares N not, it is true .

Can anyone, perhaps someone that knows Dutch or how to find the starting number, explain this?