20130622, 20:37  #78 
Jun 2009
683 Posts 
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...

20130623, 00:29  #79 
Apr 2010
Over the rainbow
2×3^{3}×47 Posts 
do you need some large n value to help?

20130623, 07:48  #80 
Jun 2009
683 Posts 
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 N1 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 N1 can be done with a helper (s+2) and for +5 a N1 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. 
20130704, 13:57  #83 
Mar 2004
3·127 Posts 
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; N1) 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. 
20130704, 15:09  #84  
Jun 2009
1010101011_{2} Posts 
Quote:
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 N1 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 N1 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. 

20130713, 10:57  #85 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×29×101 Posts 
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. 
20130713, 13:16  #86 
Jun 2009
683 Posts 
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. 
20130713, 13:59  #87 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5858_{10} Posts 
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.

20130714, 12:43  #88 
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{6} Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How/Where to get Jens Kruse Andersen's prime constellation sieve?  Stargate38  And now for something completely different  2  20170428 00:08 
Efficiently finding a linear progression in data  fivemack  Math  27  20151212 18:42 
GPU Prime Sieve  tapion64  GPU Computing  7  20140410 06:15 
Sieve depth vs. prime probability  Unregistered  Information & Answers  2  20100525 20:51 
Prime in Riesel Sieve Project  Sloth  Prime Sierpinski Project  1  20060510 02:02 