How do you efficiently sieve for prime 3/4-tuples?

[Puzzle-Peter]

Can't edit any more. I just found a mistake in my calculation for x. Dang! This will change the sieve quite a bit. I'll be back...

[firejuggler]

do you need some large n value to help?

[Puzzle-Peter]

OK, got it ( I hope...). After testing the small example I wanted to make my life easier and went a little bit too far.

Let's start at the beginning.

Like I said, I want to be able to prove all three members of a triple by N+1 or N-1 tests. So I thought about creating a triple from already known primes. The small working example used numbers of the form

N=(s+2)*(a*s^2 + b*s -2) -1/+1/+5 with s constant, a,b variable

For the -1 and +1 number, N+1 and N-1 can be done with a helper (s+2) and for +5 a N-1 test can be done with helper s. So I need s and (s+2) to be known primes, i.e. a pair of twin primes. Those are available in every reasonable size from e.g. http://www.noprimeleftbehind.net/gary/twins1M.htm

To make my life easier, I first got rid of the b*p part, wich results in

N=(s+2)*(a*s^2 -2) -1/+1/+5 which still works (again, tested on a small example to make sure I didn't miss any algebraic factorizations)

Next I thought I could simplify this whole process even more by going for N=a*(s+2)*(s^2 -2) which is wrong. This was the version my last question was based on.

So, back one step.

N=(s+2)*(a*s^2 -2) -1/+1/+5
ABC2 works for small numbers but it's way too slow for larger numbers.

Assuming I made no further mistakes, here's what I've got:
The coefficient a needs to be an even number. (After deciding which s to use, the number of possible values for a can be further reduced by eliminating a's resulting in candidates divisible by 3 or 5, that's about as far as I can think lol)
For a=2 we have a starting point of (s+2)*(2*s^2 -2)
Incrementing a by 2 increases the candidate by (s+2)*2s^2
Again I can precompute the starting point mod p and the increment mod p for a list of sieve primes p and use this information for going through a bitarray representing the a's. Which means I am stuck at the same point as before i.e. how to quickly go through the array without calculating mods for every a.

I hope I didn't make this sound like a lot of gibberish. If so, let me know and I'll try to clarify.

[kar_bon]

Twin primes also available on my page:
- see Downloads -> all primes listed in the data tables
- see Related -> First twin k: all first twin of any k-value < 15000

[Puzzle-Peter]

Originally Posted by kar_bon

Twin primes also available on my page:
- see Downloads -> all primes listed in the data tables
- see Related -> First twin k: all first twin of any k-value < 15000

Thanks!

[biwema]

If I understand you correctly, you try to find x that k*x+4 or k*x+6 or both can be factored easily (N+1; N-1) that you don’t need PRIMO. In that case there are also some restrictions for x.

Actually there are already triplets, which have a special form which can be proven with PFGW. For example, have a look at this triplet:


(99241437759 * 205881 * 4001# (205881*4001# + 1) + 210) (205881*4001# − 1)/35 + d, d = 1, 5, 7 (5132 digits, Mar 2006, Ken Davis).

If you change the parameters, you could find larger primes. Due to the special form you need an adapted sieve and the PRP as well as the sieve could be somewhat slower.

[Puzzle-Peter]

Originally Posted by biwema

If I understand you correctly, you try to find x that k*x+4 or k*x+6 or both can be factored easily (N+1; N-1) that you don’t need PRIMO. In that case there are also some restrictions for x.

I'm not sure we are talking about the same thing.

I plan to look at numbers of the form
N=(s+2)*(a*s^2 -2) -1/+1/+5
for -1 and +1, N+1 and N-1 have a helper factor (s+2)
for +5 we get
a*s^3 + 2*a*s^2 - 2*s - 4 + 5 which simplifies to
a*s^3 + 2*a*s^2 - 2*s + 1 so we can do a N-1 test with helper factor s.
That means I need s and (s+2) to be a pair of twin primes.

The variable I will be sieving is a. I know all the stuff I need is in the programs uploaded to this thread, but rearranging the pieces is quite tricky.

[henryzz]

I have been thinking about how to modify gsieve for different forms. I think I understand quite a bit of the code.
However, in the array Table each value is set to ((p+1)/2)^e%p. I don't get what this is trying to do. I am probably being stupid. Can anyone help me out by pointing me in the correct direction?

Once I understand that I think I should be able to change the sieve to k*x+c[i] where x is anything we want(currently 2^n) and c[i] are -1,+1 etc. A primorial sieve should be possible for instance.

[Puzzle-Peter]

I keep trying a far less universal approach only for the form I mentioned in my last post. So I can use the pow_mod and mod_inv functions without fully understanding what's happening inside. But the array handling stuff is far above my head.

To make things even worse, the number of sieve primes needs to be increased as well. For the usual forms of triples and quads I used gsieve to get a starting list of candidates which I then sieved further using NewPGen. For the stuff we're talking about here, all the sieving needs to be done in the program itself.

[henryzz]

Currently the memory usage is too high to sieve much deeper. However, it should be possible to split the list of primes into blocks which use a sensible amount of memory. This might potentially come at a bit of a speed cost.

[R. Gerbicz]

I'm in the process to rewrite gsieve.c for your new problem. It will be possible to sieve large primes also (so q>2^31), what gsieve currently doesn't handle.