20060731, 19:21  #1 
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 twinprimes 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 3*base^n+1, 3*base^n1, 9*base^n+1, 9*base^n1 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^n1)    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 Code:
  15  27   45  57     87   105   123    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^n1)    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 Code:
 9  21   39 45     75     105   123 129 135  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 20060731 at 19:22 
20060731, 19:44  #2 
Jun 2003
5359_{10} Posts 
So what's the problem, again?

20060731, 19:50  #3 
Nov 2004
UK
100110_{2} 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. 
20060731, 20:11  #4 
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? 
20060731, 21:40  #5 
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...

20060801, 23:31  #6 
Nov 2004
UK
2·19 Posts 
Yup, exactly what I was after  Thanks.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
PC problems  Nimras  Information & Answers  6  20091215 21:24 
Need help with few problems  Laserjet  Hardware  1  20071013 10:59 
Two problems  gribozavr  Puzzles  11  20070205 05:46 
Clock Problems  R.D. Silverman  Puzzles  5  20061213 00:29 