mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 Register FAQ Search Today's Posts Mark Forums Read

 2013-06-22, 20:37 #78 Puzzle-Peter     Jun 2009 22·132 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...
 2013-06-23, 00:29 #79 firejuggler     Apr 2010 Over the rainbow 9AB16 Posts do you need some large n value to help?
 2013-06-23, 07:48 #80 Puzzle-Peter     Jun 2009 22×132 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 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.
 2013-06-23, 08:22 #81 kar_bon     Mar 2006 Germany 2·1,427 Posts 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
2013-06-23, 08:34   #82
Puzzle-Peter

Jun 2009

22×132 Posts

Quote:
 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!

 2013-07-04, 13:57 #83 biwema     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; 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.
2013-07-04, 15:09   #84
Puzzle-Peter

Jun 2009

22·132 Posts

Quote:
 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.

 2013-07-13, 10:57 #85 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 34×71 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.
 2013-07-13, 13:16 #86 Puzzle-Peter     Jun 2009 22·132 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.
 2013-07-13, 13:59 #87 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 34×71 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.
 2013-07-14, 12:43 #88 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2×709 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 04:21.

Sun Nov 29 04:21:47 UTC 2020 up 80 days, 1:32, 3 users, load averages: 1.19, 1.38, 1.37