2
$\begingroup$

I developed a twin prime sieve and would like to know if there is a well known equivalent. Pardon my lack of proper notation. Feedback on how to format this properly would also be appreciated.

let K = some natural number
    M = 6*K^2
    N = 6*M
    S = {1,2,3,...M}
forall k in {1,2,3,...K}
    p,q = 6*k-1, 6*k+1
    A = {a : -k (mod p), a <= M}
    B = {b : k (mod p), b <= M}
    C = {c : -k (mod q), c <= M}
    D = {d : k (mod q), d <= M}
    S = S - (A+B+C+D)
T = {(6*k-1, 6*k+1) for k in S}

I have a simple python implementation of this here. A sample run for K = 2 looks like this;

K: 2  M: 24  N: 144
S: set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]) 

k: 1
  p,q: 5 , 7
      A: [4, 9, 14, 19, 24]
      B: [6, 11, 16, 21]
      C: [6, 13, 20]
      D: [8, 15, 22]
      S: set([1, 2, 3, 5, 7, 10, 12, 17, 18, 23]) 

k: 2
  p,q: 11 , 13
      A: [9, 20]
      B: [13, 24]
      C: [11, 24]
      D: [15]
      S: set([1, 2, 3, 5, 7, 10, 12, 17, 18, 23]) 

Twin Primes <=  144 :
     [(5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139)]
$\endgroup$
  • 2
    $\begingroup$ Nope. There have been a few questions asked about this one by yours truly, too. Question 1, Question 2. Here's the OEIS sequence: oeis.org/… $\endgroup$ – Geoffrey Jun 26 '17 at 2:15
  • $\begingroup$ @Geoffrey - thank you. I don't have the depth to have made that connection, so you've given me a lot to follow up on and learn. $\endgroup$ – CAB Jun 27 '17 at 13:29
  • $\begingroup$ Another "well-known equivalent" was published in American Mathematical Monthly (IIRC) as a note by Maria Suzuki, in January of 2000: $6|ab|+a+b$. This form only requires $a,b\in\Bbb Z\setminus\{0\}$. $\endgroup$ – abiessu Jun 27 '17 at 15:16
  • 1
    $\begingroup$ A good exercise would be to prove that when either $p$ or $q$ is composite, that all the numbers produced by $A,B,C,D$ are already contained by a residue class with a prime modulus in the above class of arithmetic progressions. $\endgroup$ – user1329514 Jun 28 '17 at 14:20
  • $\begingroup$ @PokerFace - I have done that, though not posted it above. Quickly, from the above, for k=1 and p=5 the values in A, while they are all -1 (mod 5) actually represent n which are all +1 (mod 5). Thus 4 represents 6*4+1 = 25. Similar for B, which are all 1 (mod 5) but represent n which are -1 (mod 5). Hence 6 represents 6*6-1 = 35. This, and a few other tricks, can be used to optimize the algorithm. $\endgroup$ – CAB Jun 28 '17 at 20:01
0
$\begingroup$

This works as a python program. You've tested it, you've run it, I recognize the math behind it and I know that it gives you the twin primes. I've been working through two definitions in particular -- compound arithmetic progressions and composite topologies -- that are full well drawn from those exact observations. Sieve theory, itself, is quite abstract and the cost of that versatility is a certain measure of ambiguity that (intentionally?) obscures solutions to problems that are notoriously easy to describe.

Notice that in your program you define four (4) arithmetic progressions. The difference between an arithmetic progression and a residue class is that an arithmetic progression has an infimum, whereas a residue class does not.

The residue class $\{a \pmod{m} \}$ represents the set of integers that when divided by the modulus $m$ produce a remainder (also residue) of $a$. Using the notation $[a]_m \in \mathbb{Z}/m\mathbb{Z}$ to represent the set $\{a \pmod{m} \}$, we can describe an arithmetic progression in the residue class by endowing the set with an infimum, or minimum value, $n$, and that would look like $[a]_m \cap [n,\infty)$ where we form the intersection with the coset of positive integers $\mathbb{Z}^+ + n - 1$, if we take $\mathbb{Z}^+$ to be defined as $[1, \infty) \cap \mathbb{Z}$ as in the ISO standard.

We can also say that the sets of residue classes formed by $[\pm k]_{6k \pm 1}$ have residues and moduli that are all arranged as linear forms sharing a common dependent variable $k$ in that they are all of the form $mk + r$.

But in carrying out the sieve process to find numbers ${n-1, n+1}$ that are both prime, as in the Sieve of Eratosthenes, it makes no sense to exclude certain residue classes beyond a certain function of $k$ as you did in the above program. In fact, it follows from the Sieve of Eratosthenes that the infimum of each residue class in the exclusion covering (the set of residue classes $[\pm k]_{6k \pm 1}$ for some positive integer $k > 0$) is specifically the sum of the residue and the modulus $a + m$. I refer to this as the summand infimum and use the notation $[a]^+_m = \{ a \pmod{m} \} \cap [a+m,\infty)$ to indicate the intersection between the residue class and the coset of the positive integers.

The consensus is that, indeed the set of twin primes is represented by the following expression, across the positive integers $k > 0$:

$$ \mathbb{Z}^+ \setminus \bigcup\{ [k]^+_{6k+1}, [-k]^+_{6k+1}, [k]^+_{6k-1}, [-k]^+_{6k-1} \} $$

It's easier to call the terms $[\pm k]^+_{6k \pm 1}$ in the above compound arithmetic progressions. The definition for compound arithmetic progressions that I give in Prime Gaps in Residue Classes is rock solid. The definition I give for composite topology, however has the caveat in that one cannot assume that the translation scalar for the compound arithmetic progressions is always zero, but it works out just fine for 6, which is the principal modulus that I use for the De Polignac sequence in my answer to this post about Large Gaps.

Why Compound Arithmetic Progressions and Composite Topologies? Because with few restrictions they both have a provable, but elusive decomposition property whereby the residue classes contained by each can be decomposed into the intersection of residue classes with prime moduli and congruent residues through the reverse application of the ancient Chinese Remainder Theorem by Sun Tsu.

And further, even if I'm not a respected analytical number theorist, we can note that a general estimate for any CAP with a constant principal modulus and relatively prime commutative residues is going to depend on a sum:

$$ \sum_{k=2}^{\infty}\frac{\pi_k(n) \sum_{j=1}^{k}(\tau_j(a) + \tau_{k-j}(d)) }{\phi(c)^k}$$

where $k$ is the number of prime factors, $\pi_k(n)$ is the almost prime counting function, $\phi(c)$ is the result of Euler's totient function for the principal modulus and $\tau_k$ is the $k$-fold divisor function for the multiplicative group $(\mathbb{Z}/c\mathbb{Z})^*$.

There is a heuristic that makes this extensible to intersections and through inclusion-exclusion unions as well, but we're only looking at CAPs with commutative residues that are relatively prime to the principal modulus. In order to lift the restriction on the commutative residues, we would need to know more about the homomorphic subgroups.

The estimate for a composite topology reduces to the estimate for primes in an arithmetic progression.

$$ n - \pi(n, q, a)$$

where $q$ is the principal modulus and $a$ is the determinant residue.

You might be able to "prove" the admissibility of a k-tuple without using a similar method but I don't think its likely, and my response to Asypmtotic expressions... implies the utility of this method in studying the k-Tuple Conjecture.

$\endgroup$
  • $\begingroup$ Thank you for taking the time and effort on this. I really appreciate this. $\endgroup$ – CAB Jul 8 '17 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.