mersenneforum.org Sieving Problems
 Register FAQ Search Today's Posts Mark Forums Read

 2006-07-31, 19:21 #1 amcfarlane     Nov 2004 UK 2×19 Posts Sieving Problems I've been trying to understand a particular method for sieving and seem to be having some problems. I'm searching for twin-primes of the form k.base^n+/-1 where k is odd and n is fixed. Now I know that all twin primes (excluding {3,5}) have the form 6n+/-1, so I'm creating a bitfield of k's where k = 3 (mod 6): Code:  3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99 105 111 117 123 129 135 141 Now, I'm confident that I don't have to trial divide each full expression: 3*base^n+1, 3*base^n-1, 9*base^n+1, 9*base^n-1 etc, if nothing else, it's going to be darn slow, so I just need to be looking at the individual values of k (along with my base and n values). For example: (Assuming base=2, n=2, and k is the range above) Code: Divisor Remove K (for k.base^n+1) Remove K (for k.base^n-1) ------- ------------------------- ------------------------- 2 none none 3 none none 5 21, 51, 81, 111, 141 9, 39, 69, 99, 129 7 33, 75, 117 9, 51, 93, 135 11 63, 129 3, 69, 135 Leaving: Code:  - - 15 -- 27 -- -- 45 -- 57 -- -- -- -- 87 -- -- 105 --- --- 123 --- --- --- Now, by changing the base and/or n, the relative start point of the sieve differs. For example: (Assuming base=2, n=3, and k is the range above) Code: Divisor Remove K (for k.base^n+1) Remove K (for k.base^n-1) ------- ------------------------- ------------------------- 2 none none 3 none none 5 3, 33, 63, 93 27, 57, 87, 117 7 27, 69, 111 15, 57, 99, 141 11 15, 81 51, 117 Leaving: Code:  - 9 -- 21 -- -- 39 45 -- -- -- -- 75 -- -- -- -- 105 --- --- 123 129 135 --- As you can see, the sequence is different, albeit we are using the same divisors. Now (and finally you may say), how do I calculate the start position of the sequence for a given base and n value? (I have been using NewPGen however, I'm having some difficulty in rewriting it to work on by AM64/BSD boxes.) Last fiddled with by amcfarlane on 2006-07-31 at 19:22
 2006-07-31, 19:44 #2 axn     Jun 2003 535910 Posts So what's the problem, again?
 2006-07-31, 19:50 #3 amcfarlane     Nov 2004 UK 1001102 Posts Given a fixed base and a fixed n, I can perform the sieve easily, but if I change either the base or n, the sieve needs to be adjusted so that the correct values of K are removed ~without~ examing k.base^n+/-1. Looking at my examples above, in the first example I was able to remove the 1st, 2nd, 4th ... numbers from the list of possible k's, however the second example, I removed the 1st, 3rd, 5th.. k's. Knowing where the sieve starts relative to the initial (k_min . base^n +/- 1) is the solution - it has to be a simple "mod" operation but I'm darned if I can see it.
 2006-07-31, 20:11 #4 axn     Jun 2003 23×233 Posts Suppose p divided k*b^n+1 (just the +1 case) i.e. k*b^n+1 = 0 (mod p) => k*b^n = -1 (mod p) => k = -b^-n (mod p) b^-n can be calculated as either (b^n)^-1 or (b^-1)^n [Here ^-1 is the modular inverse calculation] Since you are looking only at k which are multiples of 3, you can quickly check which of k, k+p, or k+2p is divisible by 3 and use that as the "correct" starting point. WARNING -- the above discussion only covers the +1 series. Don't forget the -1 series also. Is that what you were looking for?
 2006-07-31, 21:40 #5 amcfarlane     Nov 2004 UK 2×19 Posts I think it might well be... although I admit to not being familiar with the modular inverse -- it does appear to be rather handy. Just testing some code...
 2006-08-01, 23:31 #6 amcfarlane     Nov 2004 UK 2·19 Posts Yup, exactly what I was after - Thanks.

 Similar Threads Thread Thread Starter Forum Replies Last Post JHansen NFSNET Discussion 9 2010-06-09 19:25 Nimras Information & Answers 6 2009-12-15 21:24 Laserjet Hardware 1 2007-10-13 10:59 gribozavr Puzzles 11 2007-02-05 05:46 R.D. Silverman Puzzles 5 2006-12-13 00:29

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

Tue May 17 21:33:55 UTC 2022 up 33 days, 19:35, 0 users, load averages: 1.48, 1.50, 1.39