Sierp base 3 reservations/statuses/primes

[gd_barnes]

I've sent an email to michaf asking for his status on his Sierp base 3 reservation and his base 24 reservations on both sides.


Gary

[mdettweiler]

Originally Posted by gd_barnes

k's divisible by 3^2 resulting in a k with no prime:
k's divisible by 3^1 resulting in a k with no prime:

Doesn't a k with no prime mean that the conjecture can be no higher than that k?

[gd_barnes]

Originally Posted by Anonymous

Doesn't a k with no prime mean that the conjecture can be no higher than that k?

no known prime

[geoff]

Here is a rough diagram showing where I think the different methods for sieving k*2^n+/-1 are efficient.

many k
values
  ^
  | NewPGen                   same number of
  |(fixed-n)                  k  and n values
  |                                 /
  |                               /
  |                             /
  |                           /
  |                         /
  |                       /
  |                     /
  |               gcwsieve
  |                 /
  |               /
  |             /
  |           /
  |         /         srsieve
  |       /                      sr2sieve     proth_sieve/JJsieve
  |   trial                                     (SPH algorithm)
  | factoring           
  |/              NewPGen (fixed-k)    sr1sieve
  +---------------------------------------------------> many n values

gcwsieve only works for k=n, but the basic algorithm could be generalised.

For an extreme case like the initial stages of Base 3 Sierpinski/Riesel, the ideal sieve would probably be found in the area above the diagonal. This would be a sort of fixed-n sieve that works with multiple n-values.

[mdettweiler]

Originally Posted by gd_barnes

no known prime

Oh, I see.

[KEP]

@Gary, you can sure change it, maybe I should just bring it up to n=100,000, so you can do that. No problem at all Good luck on getting your pages done. I'll check back later tonight, if no one has taken the sierpinski gap and reserved it, I'll throw in my last free ressoruce and start working on that range, but of course I'll tell in the base 3 forum weather or not I take it

[KEP]

Reenforcement has arrived. 1 quad Q6600 has been thrown into the war. So for now work seems to be done in this way:

1. No reservation of sierpinski base 3
2. Test all sierpinski base 12 candidates up to n=250,000 or prime found
3. Test all riesel base 27 candidates up to n=1,000,000 or prime found
4. Test all sierpinski base 19 candidates up to n=100,000 or primes found
5. Continue on the base 3 riesel conjecture

Regards

KEP

[gd_barnes]

Originally Posted by KEP

Reenforcement has arrived. 1 quad Q6600 has been thrown into the war. So for now work seems to be done in this way:

1. No reservation of sierpinski base 3
2. Test all sierpinski base 12 candidates up to n=250,000 or prime found
3. Test all riesel base 27 candidates up to n=1,000,000 or prime found
4. Test all sierpinski base 19 candidates up to n=100,000 or primes found
5. Continue on the base 3 riesel conjecture

Regards

KEP

That's a mother load. Thanks for bringing in that quad! All reservations are reflected on the web pages now.

With the exception of Siemelink's recent primes on Riesel base 19, the CRUS pages should be fully up to date.


Gary

[gd_barnes]

Originally Posted by geoff

Here is a rough diagram showing where I think the different methods for sieving k*2^n+/-1 are efficient.

many k
values
  ^
  | NewPGen                   same number of
  |(fixed-n)                  k  and n values
  |                                 /
  |                               /
  |                             /
  |                           /
  |                         /
  |                       /
  |                     /
  |               gcwsieve
  |                 /
  |               /
  |             /
  |           /
  |         /         srsieve
  |       /                      sr2sieve     proth_sieve/JJsieve
  |   trial                                     (SPH algorithm)
  | factoring           
  |/              NewPGen (fixed-k)    sr1sieve
  +---------------------------------------------------> many n values

gcwsieve only works for k=n, but the basic algorithm could be generalised.

For an extreme case like the initial stages of Base 3 Sierpinski/Riesel, the ideal sieve would probably be found in the area above the diagonal. This would be a sort of fixed-n sieve that works with multiple n-values.

That's an interesting graph, Geoff.

Can you clarify your last statement? Do you mean a fixed-n sieve that works with multiple k-values or a fixed-k sieve that works with multiple n-values?

So based on this, what software do you feel would work best for sieving base 3? It almost looks like srsieve sieving many k's across a somewhat narrower n-range because there are SO many k's for base 3 and it's such a prime base. But I know sr2sieve has been improved a lot to handle many k's.

Also, you said gcwsieve could be generallized. Does that mean that the program can be changed so that k does not have to equal n?

Thanks for the info.


Gary

[geoff]

Originally Posted by gd_barnes

Can you clarify your last statement? Do you mean a fixed-n sieve that works with multiple k-values or a fixed-k sieve that works with multiple n-values?

I mean a fixed-n sieve that accepts multiple n values, analogous to srsieve which is a fixed-k sieve that accepts multiple k values.

So based on this, what software do you feel would work best for sieving base 3? It almost looks like srsieve sieving many k's across a somewhat narrower n-range because there are SO many k's for base 3 and it's such a prime base. But I know sr2sieve has been improved a lot to handle many k's.

I don't know of any existing software that is efficient for sieving the early stages of base 3. Trial factoring with PFGW then sieving in batches with srsieve is probably the best that you can do with existing software.

Also, you said gcwsieve could be generallized. Does that mean that the program can be changed so that k does not have to equal n?

In principle yes. The algorithm used by gcwsieve is a sort of mass trial-factoring algorithm, but instead of computing each trial independantly it re-uses some of the computations from the previous trial. The case where n=k is particularly simple to code and only requires one modular multiplication per k,n pair for each trial factor. The general case would be more complicated to code but would probably require no more than two modular multiplications per k,n pair. (This is still much less efficient than a fixed-k sieve with a large n-range or a fixed-n sieve with a large k-range however).

Having said that I should make it clear that I am not planning to write any such programs in the near future, I don't have the time.

[gd_barnes]

Originally Posted by geoff

I mean a fixed-n sieve that accepts multiple n values, analogous to srsieve which is a fixed-k sieve that accepts multiple k values.



I don't know of any existing software that is efficient for sieving the early stages of base 3. Trial factoring with PFGW then sieving in batches with srsieve is probably the best that you can do with existing software.



In principle yes. The algorithm used by gcwsieve is a sort of mass trial-factoring algorithm, but instead of computing each trial independantly it re-uses some of the computations from the previous trial. The case where n=k is particularly simple to code and only requires one modular multiplication per k,n pair for each trial factor. The general case would be more complicated to code but would probably require no more than two modular multiplications per k,n pair. (This is still much less efficient than a fixed-k sieve with a large n-range or a fixed-n sieve with a large k-range however).

Having said that I should make it clear that I am not planning to write any such programs in the near future, I don't have the time.

Now I get it. Speaking of the fixed-n sieve with multiple n-values, it makes me wonder if using NewPGen with the increment counter set on would work well for this. That's what I use for my 'all twin prime search' where I sieve all k<1M for 1000 n-values at a time. It's not extremely efficient but it is the most effective way I know of for twin prime searching.

I think I'll play around with NewPGen here. The fact that it's such a prime base with so many k's may make it a possibility. I never thought I'd say that about NewPGen again except for special multiple-prime forms such as twins, SG's, etc. But it may make sense, as KEP has alluded to, to use PFGW to a very small n-value (perhaps n=2500 or less) and leave thousands or even millioins of k's remaining and then use NewPgen with the increment counter set on to sieve a large range of those k across one n-value at a time. With base 3 being such a prime base, that might be a possibility.

For that matter, perhaps we shouldn't use PFGW trial factoring at all! Maybe we could sieve billions of k's at once starting at n=1 with NewPgen's increment counter and go up from there. Of course, then you get into the issue of huge file sizes requiring more manual intervention, the fact that NewPGen (or any sieving software for that matter) doesn't actually do prime searching so it continues sieving k's after primes would have been found, etc.

Thanks for your input.


Gary