Sierp base 3 reservations/statuses/primes

[gd_barnes]

Originally Posted by KEP

Thanks Paul, your post actually just solved the issue mentioned in my previous post. Plus it creates a much smaller log file when doing only PRP tests. So now my command line Gary sounds like this:

"input.txt -l5M.txt" and when done sieving I will use this command line:

"pfgw.log -tp" this will be sufficient and very time consuming, since a lot of tests can very fast be verified up to max n or 25,000 which is my limit :)

So thanks Paul, and of course also to you Gary for helping out that much you did. Maybe if we implemented these lines at all tests, we would really start to see some improvement in speed. Anyway I'll now continue the Base3 attack and launch the major attack from Wednesday, maybe earlier, if I see the Sierpinski range complete in early time :)

Thanks and take care everyone.

KEP!

Ps. Gary you doesn't have to reply to my PMs regarding my problem which is now solved, but if you do that prior to reading this post its also OK, since one enjoys reading science stuff and other peoples solutions to issues occorring :)

KEP,

Sorry. I had not actually tried a primality proof when doing base 3. I always just did the PRP test and later proved them. I was thinking by your prior statements that he did not want 2 output files, one for proven primes and one for PRP's and didn't think it would take so much longer.

But I guess I'm confused. I don't see how Paul's recommendation is any different than what I recommended that you do originally. You're still going to get two output primes files, one for proven primes and one for PRP's and you'll still need to look in the pfgw.out file to determine what k's are remaining at the end. To me, that is still the most efficient way.

I will say this...it can be extremely tricky starting a new base and I generally don't recommend it for new searchers. You've probably found out why. (lol)


Paul,

Thanks for stepping in. We don't really need a sieve for base 3 below n=~25000. Although it might be a little more CPU-efficient to start a sieve for all k's remaining at n=~15000, it involves more manual work.

But are you saying that PFGW can sieve on the fly for you? Isn't that what -f100 is effectively doing...actually, prefactoring to 100% of what it 'should be' for each individual test...less efficient than sieving but is a good tradeoff to avoid a lot of manual intervention.

Can you clarify the exact most efficient command line to use when searching upwards by k-value? I thought I had it with the originally script and command line before suggesting the -tp method, which obviously was a mistake.


Gary

[KEP]

Originally Posted by gd_barnes

But I guess I'm confused. I don't see how Paul's recommendation is any different than what I recommended that you do originally. You're still going to get two output primes files, one for proven primes and one for PRP's and you'll still need to look in the pfgw.out file to determine what k's are remaining at the end. To me, that is still the most efficient way.

It isn't much different. But it appears to be more efficient to do a PRP prime test, and then verify that file. I actually don't care about getting a verification at once or weather to get PRP needing to be verified later. In the end, it appears to be faster to do a PRP test first, and then verify in the end. Sorry if I gave you the impression that I didn't wanted to do any PRP verification after doing the first runs tests. On a sidenote however I can recommend to do PRP tests, since it creates a lot smaller log file, and since there seems to be some sort of issue that the developers of PFGW has to adress with doing a complete proof of any PRP found on the fly, since at some state it fails to complete, and appears to loop a weird mathematic calculation, in wain and then one is loosing a lot of computation power on nothing. Anyway, I understand why you don't recommend anyone to start up a range by them selves, but now I've found out what to do, and how to adress the attack. This will make sure that all primes is found. So no problem any further, but again if I had not had this Forum to ask to, I would never have solved this one on my own.

And again Paul, thanks for clearing out this option :) Expect to be at, at least 1M k tomorrow. So far I'm at 100k k's and no k's left to test. The last one failed at N=~5,300, so for now, no k's left to test below k=100,000 :)

Thanks for all your support, and now I expect a huge progress to be coming. And again Gary it's hard for me to say weather or not there is much difference in what Paul or you told me (adviced me) to do. And I'm sorry if I've confused you and not fully answered your question. But hey I'm expecting to be going strong on this attack at the Base3 conjecture. And finally, no hard feelings from here ;)... since this is a great project, and one can work offline for weeks on this one. I will stribe to do a weekly or biweekly update of my google page, so you can follow the progress on the range, but expect really nothing to happen before wednesday :)

Take care everyone!

KEP!

[paulunderwood]

Originally Posted by gd_barnes

Paul,

Thanks for stepping in. We don't really need a sieve for base 3 below n=~25000. Although it might be a little more CPU-efficient to start a sieve for all k's remaining at n=~15000, it involves more manual work.

But are you saying that PFGW can sieve on the fly for you? Isn't that what -f100 is effectively doing...actually, prefactoring to 100% of what it 'should be' for each individual test...less efficient than sieving but is a good tradeoff to avoid a lot of manual intervention.

Can you clarify the exact most efficient command line to use when searching upwards by k-value? I thought I had it with the originally script and command line before suggesting the -tp method, which obviously was a mistake.


Gary

Sieving the whole range is a lot quicker than trial dividing all the numbers one by one. Use NewPGen. Time a PFGW PrP test at 80% of you maximum "n". For example, if your maximum "n" is 150k then time one number with PFGW at n=120k. Then use NewPGen until your removal rate becomes as long the your timed test (with PFGW at 80% of the maximum of the range.)

With what is left from sieving, do PrP tests with PFGW. The full primality tests will take much longer to do than probable prime tests; this soon mounts up the time if you have many thousands to do -- why take 5 weeks on a batch when you can do it in 1 week?

The probable prime tests indicate that a number might be prime -- all primes will be included in the PrP list, but there is a remote mathematical chance that a composite number will be in it too. So you need to prove them, which can be done with the N+1 classical test (-tp) for Riesel type numbers that PFGW implements.

Summing up:
1.) time PFGW at 80% of your range
2.) sieve with NewPGen until the removal rate equals 1.)
3.) PrP test what remains with PFGW
4.) prove any PrPs found, with PFGW's "-tp" switch

[gd_barnes]

Originally Posted by paulunderwood

Sieving the whole range is a lot quicker than trial dividing all the numbers one by one. Use NewPGen. Time a PFGW PrP test at 80% of you maximum "n". For example, if your maximum "n" is 150k then time one number with PFGW at n=120k. Then use NewPGen until your removal rate becomes as long the your timed test (with PFGW at 80% of the maximum of the range.)

With what is left from sieving, do PrP tests with PFGW. The full primality tests will take much longer to do than probable prime tests; this soon mounts up the time if you have many thousands to do -- why take 5 weeks on a batch when you can do it in 1 week?

The probable prime tests indicate that a number might be prime -- all primes will be included in the PrP list, but there is a remote mathematical chance that a composite number will be in it too. So you need to prove them, which can be done with the N+1 classical test (-tp) for Riesel type numbers that PFGW implements.

Summing up:
1.) time PFGW at 80% of your range
2.) sieve with NewPGen until the removal rate equals 1.)
3.) PrP test what remains with PFGW
4.) prove any PrPs found, with PFGW's "-tp" switch

?? No...I think it's still not clear what I'm asking. I'm fully aware of virtually everything you've stated here.

You can't use NewPGen to sieve multiple k's and n's! That's what we are asking about. We're using PFGW to test from k=1 to k=1M to n=25K while prefactoring with it on the fly using the -f100 switch. NewPGen can only sieve one k at a time when sieving across multiple n. Is there something new that I'm unaware of in NewPGen? Technically NewPGen should NEVER be used except for twins and other special prime forms. 1 or 2 k's, use sr1sieve. More than 2 k's use sr2sieve.

It would be highly inefficient to use NewPGen at any step in this. Even using speedy sr2sieve would be inefficient below n=5K on such a prime base. 95-99% of all k's are eliminated below n=5K on this base by PFGW with no sieving done at all. There's no reason to sieve the entire n-range.

Below is what Micha and I have been using that works very well for base 3. It is what I have used to test Sierp base 3 for k=1 to 10M!:

File input-sierp-base3.txt script:
ABC2 $b*3^$a+1 // {number_primes,$b,1}
a: from 1 to 25000
b: from 2 to 1000000 step 2

Command line:
input-sierp-base3.txt -f100 -l

We then decided that we'll use sr2sieve to sieve all k's that don't have primes for n<=25K.

PFGW can run the above in less than 2 CPU days and all you have to do is look at the pfgw.out file for k's remaining. The file can be 300-400 MB but after waiting a minute for it to pull up, there's no problem. The primes are in pfgw-prime.log and the PRP's are in pfgw.log so you then just run the -t test on the PRP's, which only takes 1-3 hours.

Alternatively, it might be more efficient to only go to n=10K instead of n=25K but this has been my choice to avoid having so many k's thrown into a big sieve later on.

I simply don't understand what I am missing in all of this.

KEP, is the above what you are doing or are you doing any sieving beforehand? If so, what is it that you are using to sieve? IMHO, no sieving is needed at all below n=10K. A case could be made for sieving above n=10K but I prefer to just let PFGW run to n=25K without sieving.


Gary

[gd_barnes]

Originally Posted by gd_barnes

OK, I will change your reservation from k=110M-111M to 110M-120M.

I responded to your PM on the Riesel conjecture. The script on the input file would be the same except -1 instead of +1. Like the Sierp conjecture, only even k's need to be tested so no change there.

But there is a slight change on the command line. Instead use:

input.txt -f100 -l100k.txt -tp


The -tp switch tells it to prove the primality of "-1" numbers vs. "+1" numbers.

Good luck and thank you for attacking these huge bases!


Gary

Originally Posted by Anonymous

Actually, no. -tp signifies that PFGW should do an N+1 test (as opposed to an N-1 test with just plain -t), which can be used for numbers that an N-1 test can't prove primality for. (I've run into those occasionally.) Both N-1 and N+1 tests are not dependent on any form of number, so either should work for both +1 and -1 numbers.

Originally Posted by axn1

Actually, to successfully run an N+1 primality test, N+1 must be factored to atleast 33% of its length (meaning, if N is 100 digits, then at least 33 digits worth of prime factorization should be known). Vice versa for N-1. If the 33% factorization criteria is not met, then the test can't "prove" the primality.

Since N+1 factorization of a "-1" number is trivial, it makes sense to use N+1 for "-1" (and N-1 for "+1" numbers).

As I stated originally for KEP's Riesel testing and without getting into the technical details of this; if you wish to prove the following:

Riesel numbers (-1) tests; use the -tp switch in PFGW

Sierpinski numbers (+1) tests; use the -t switch in PFGW


For all other forms, a good starting point it to try -tc, which effectively attempts to prove the number prime using both of the above but is very unlikely to do so if it is a random form.

For numbers with random forms and (I think) < 10000 digits, Primo is the best way that I know how to prove them.


Gary

[paulunderwood]

Originally Posted by gd_barnes

?? No...I think it's still not clear what I'm asking. I'm fully aware of virtually everything you've stated here.

You can't use NewPGen to sieve multiple k's and n's! That's what we are asking about. We're using PFGW to test from k=1 to k=1M to n=25K while prefactoring with it on the fly using the -f100 switch. NewPGen can only sieve one k at a time when sieving across multiple n. Is there something new that I'm unaware of in NewPGen? Technically NewPGen should NEVER be used except for twins and other special prime forms. 1 or 2 k's, use sr1sieve. More than 2 k's use sr2sieve.

It would be highly inefficient to use NewPGen at any step in this. Even using speedy sr2sieve would be inefficient below n=5K on such a prime base. 95-99% of all k's are eliminated below n=5K on this base by PFGW with no sieving done at all. There's no reason to sieve the entire n-range.

Without doing comparison tests, I still feel it is quicker to sieve using the appropriate switches of NewPGen or sr2sieve called from a loop in a batch file; I might be wrong.

Originally Posted by gd_barnes

Below is what Micha and I have been using that works very well for base 3. It is what I have used to test Sierp base 3 for k=1 to 10M!:

File input-sierp-base3.txt script:
ABC2 $b*3^$a+1 // {number_primes,$b,1}
a: from 1 to 25000
b: from 2 to 1000000 step 2

Command line:
input-sierp-base3.txt -f100 -l

We then decided that we'll use sr2sieve to sieve all k's that don't have primes for n<=25K.

PFGW can run the above in less than 2 CPU days and all you have to do is look at the pfgw.out file for k's remaining. The file can be 300-400 MB but after waiting a minute for it to pull up, there's no problem. The primes are in pfgw-prime.log and the PRP's are in pfgw.log so you then just run the -t test on the PRP's, which only takes 1-3 hours.

Alternatively, it might be more efficient to only go to n=10K instead of n=25K but this has been my choice to avoid having so many k's thrown into a big sieve later on.

There is a smarter way to get those "k"'s without a prime: break a loop if a PrP (or prime) is found; Check they are prime afterwards; List those "k"s that do not have a prime.

[gd_barnes]

Originally Posted by paulunderwood

Without doing comparison tests, I still feel it is quicker to sieve using the appropriate switches of NewPGen or sr2sieve called from a loop in a batch file; I might be wrong.


There is a smarter way to get those "k"'s without a prime: break a loop if a PrP (or prime) is found; Check they are prime afterwards; List those "k"s that do not have a prime.

Ah, OK. You're talking about running batch processes in loops on these whereas I was "pigeon-holed" on manual running of PFGW and sieving.

You're right, to run billions/trillions of k's, we will definitely have to set up some sort of looping batch process.

I ran 5 million k's with 36 remaining at n=25K using the way I showed but it did require more manual intervention than I would have liked. I definitely wouldn't want to do it for billions of them. Those 36 k's remaining are listed on the Sierp base 3 reservations page.

I think base 3 will be fun for all of the programmers to automate the finding of primes, prp's, k's remaining, etc. out there. I'll leave it up to the programming gurus here to determine the quickest way to set up a batch process or something like that, although I may take a hack at it myself in the future.

Thanks for clarifying.


Gary

[paulunderwood]

Originally Posted by myself

There is a smarter way to get those "k"'s without a prime: break a loop if a PrP (or prime) is found; Check they are prime afterwards; List those "k"s that do not have a prime.

With a little searching on PrimeForm's messages, as far as I can tell, the PFGW loop Gary gives is "breaking". I apologize for the confusion.

[gd_barnes]

I'm unreserving k=30M-100M for Sierp base 3. I'll start on k=10M-30M today.

I bit off a little more than I cared to chew there.

[gd_barnes]

I've added this new thread for all correspondance related to base 3 including but not limited to reservations, statuses, primes, results files, and questions.

All prior correspondance has been moved here.


Thanks,
Gary

[gd_barnes]

KEP reported completion of the k=110M-120M range on Sierp base 3 in an Email on April 25th.

KEP, there are some changes in your k's remaining for k=110M-120M on Sierp base 3. Many of the k's are divisible by powers of 3, which results in the following changes:

The following k's were removed:
k             comments
115381692     k/3^3=4273396 already found remaining by k<10M testing
117904734     k/3^4=1455614 already found prime at n=33885 by k<10M testing
 
k's divisible by 3^2 resulting in a k with no prime:
k             k changed to     comments
113061654     12562406       k not divisible by 3^3
113975118     12663902       (same)
118690038     13187782       (same)
119820906     13313434       (same)
 
k's divisible by 3^1 resulting in a k with no prime:
k             k changed to     comments
111055104     37018368       k/3^2=12339456 has a prime at n=1
                             k/3^3=4113152 has a prime at n=2
111190494     37063498       k not divisible by 3^2
111474414     37158138       k/3^2=12386046 has a prime at n=1
                             k/3^3=4128682 has a prime at n=2
111480438     37160146       k not divisible by 3^2
112607754     37535918       (same)
114584604     38194868       (same)
115059138     38353046       (same)
116413062     38804354       (same)
116433444     38811148       (same)
116849496     38949832       (same)
117573882     39191294       (same)
117860586     39286862       (same)
117965964     39321988       (same)
118295616     39431872       (same)
119429652     39809884       (same)
119503128     39834376       (same)

For the only remaining non-reduced k that is divisible by 3, k=114121992, k/3=38040664 gives a prime at n=1 so k=114121992 remains.

This leaves a total of 67 k's remaining for the range that you tested, although only 47 k's are technically remaining for n=110M-120M.

This was difficult to get exactly correct because we have the huge gap in k-range testing. Once we get contiguous testing up to n=50M, these higher ranges should be far easier. It will be easy to determine which k-values can be eliminated, either ahead of time, or before starting sieving and listing k's remaining.

These changes are reflected on the Sierp base 3 reservations page.

Anon, now, you can see why I didn't want to start any team sieve yet. This stuff is never as easy as it appears at a glance. Testing contiguous k-ranges is a must on large conjectures before beginning sieving. When we do start sieving, I will still recommend that we sieve only contiguous k-ranges, which when we hit 100 k's remaining, will likely be for k<30M. Another option is to sieve every k-range of 50M, which will likely have us sieving about 200 k's remaining at once, which wouldn't be bad for this very prime base. That would make the k-ranges nice and round.

Now: On to determining k's with algebraic factors on Siemelink's Riesel base 19. Whew, bases 3 and 19 are a lot of work to administer but FUN! :-)


Gary