How do we identify twin primes .

Question

as known , each prime number greater than 3 is of the form $6k-1$ or $6k+1$ .

twin primes are all sort of two adjacent primes of difference $= 2$ as:

$$(11,13) ,(17,19),\ldots,(6k-1,6k+1)$$

-Is there a specific polynomial class complexity algorithm or mathematical expression which by we can know whether a given $(6k-1,6k+1)$ is twin prime couple or not without general number sweeping ?

Answer 1

There is a trivial algorithm. All twin primes produce composites of the form $X^2-1$. An interesting property of even perfect squares minus 1 (which are always composite) is the triviality of their smallest prime factor unless they are twin-prime composites. This makes it extremely fast to factor them and easy to determine the instances of twin primes (simply by elimination). The rule is that the smallest prime factor of a non-twin-prime $X^2-1$ composite cannot be greater than the square root of its square root - and usually much smaller. If such a factor is not found, the composite must be the product of twin primes. Thus the largest of these non-twin-prime factors less than $10^{12}$ is $991$ for $999836006723$.

I wrote an Excel program that exploits this. http://www.naturalnumbers.org/TwinPrimeCalc.xlsm

Answer 2

The reason you are able to use 6k to narrow your search to 1 in 3 even numbers is due to the fact that 6 is a primorial (2*3) and any twin prime couple [tpc] > 6 must satisfy the inequalities

 tpc <> +-1 (MOD 2)
 tpc <> +-1 (MOD 3) 

Leaving just one solution (MOD 6)

tpc = 0 (MOD 2) and tpc = 0 (MOD 3)

Which means that tpc = 0 (MOD 6)

This can be extended beyond the first two primes so that for example taking the first 3 primes:

The primorial P3# = 2 * 3 * 5 = 30

Any twin prime couple > 30 must satisfy the inequalities:

 tpc <> +-1 (MOD 2)
 tpc <> +-1 (MOD 3) 
 tpc <> +-1 (MOD 5) 

This means we have the same conditions as above but with the added constraint that tpc = 0,2 or 3 (MOD 5)

So we need to check 0,6,12,18,24

Of which

    0 = 0 (MOD 5)
    6 = 1 (MOD 5)
   12 = 2 (MOD 5)
   18 = 3 (MOD 5)
   24 = 4 (MOD 5)

So only 0, 12 and 18 satisfy the new constraint (MOD 30)

Now we can restrict our search to 30k, 30k+12, 30k+18 when searching for twin prime couples above 30 (not sure what the lower limit is but it's definitely not higher than this).

You're now only checking 1 in 5 (3 out of every 15) even numbers instead of your current 1 in 3.

Of course this can be extended to the 4th primorial and further for better efficiency with larger numbers.

Answer 3

The corollary to the following theorem is "a mathematical expression by which we can know whether a given $(6m-1,6m+1)$ is a twin couple or not." I leave it to others to debate whether it falls outside of "general number sweeping."

Numbers of the form $6k \pm 1$, that is, all numbers having no factors of $2$ or $3$, form a semigroup closed under multiplication. Consequently, composite numbers in that semigroup have proper factors in that semigroup.

Consider composite numbers of the form $n=(6m-1)(6m+1)=36m^2-1$.

If $p_i \le 6m-1$ is a prime divisor of $n$, then $\exists s_j = \frac{n}{p_i} \ge 6m+1$. $p_i<s_j$ and $s_j$ has the form $6k \pm 1$

$n$ is a semiprime $\iff (6m-1,6m+1) \in \mathbb P \iff (6m-1,6m+1)$ are twin primes.

If $n$ is not a semiprime, it has at least one prime factor $p_i<6m-1\\$

Theorem: If $p_i=6a \pm 1 \le 6m-1 \land p_i \mid 36m^2-1$, then $m \equiv \pm a \bmod p_i$

Case 1: $p_i=6a-1 \Rightarrow s_j=\frac{36m^2-1}{p_i}=6(a+k)+1$. $$36m^2-1=(6a-1)(6(a+k)+1) \\ 36m^2-1=36a^2+36ak+6a-6a-6k-1 \\ 36m^2=36a^2+36ak-6k$$ Since $36$ divides the LHS, $36$ must divide the RHS, so $k=6n,\ n \ge 0$. $\ n=0$ is formally allowed because $s_j=6a+1 > p_i=6a-1$, consistent with $p_i < s_j$. Substituting $$m^2=a^2+6an-n \\ m^2-a^2=(m-a)(m+a)=n(6a-1)=n\cdot p_i \\ m \equiv \pm a \bmod p_i$$

Case 2: $p_i=6a+1 \Rightarrow s_j=\frac{36m^2-1}{p_i}=6(a+k)-1$. $$36m^2-1=(6a+1)(6(a+k)-1) \\ 36m^2-1=36a^2+36ak-6a+6a+6k-1 \\ 36m^2=36a^2+36ak+6k$$ Since $36$ divides the LHS, $36$ must divide the RHS, so $k=6n,\ n > 0$. $n=0$ is not formally allowed, because in that case $s_j=6a-1 < p_i=6a+1$, which is inconsistent with $p_i < s_j$. Substituting $$m^2=a^2+6an+n \\ m^2-a^2=(m-a)(m+a)=n(6a+1)=n\cdot p_i \\ m \equiv \pm a \bmod p_i$$

Corollary: $6m-1,6m+1 \in \mathbb P \iff \forall a<m,\ m\not \equiv \pm a \bmod p_i$. Note that this corollary excludes the case $a=m$, for which $m\equiv a$ by any modulus. If $m=a$ (whence $n=0$ and $b=a$) is the only instance where $m \equiv \pm a \bmod p_i$, then $6m-1,6m+1$ are twin primes.

Note that this formulation does not resolve the twin prime conjecture. However, if the twin prime conjecture is false, then there exists some $m_0$ such that for all $m>m_0$, $m \equiv \pm a \bmod p_i$ for some $p_i=6a \pm 1 < 6m-1$.

Answer 4

Currently, there is not such non-trivial algorithm or mathematical expression, and indeed still there is not a demonstration about the infinity of the twin primes. More than looking for the algorithm to find twin prime couples, I would dare to say that the aim is to understand the distribution of prime numbers, first of all, and then to understand the distribution of other type of special prime numbers.

Just in case, the wikipedia is a good starting point. I am also interested in this kind of topics, for instance you can see some test about the total number of twin primes in the vicinity of twin primes in this question.

Answer 5

i have a solution using prime generating polynomials

from thousands of polynomials which can extract billions of primes within specific range , i chose to deal with euler polynomial

$$n²+n+p$$

with :

• $4p-1$ is a Heegner number $\epsilon\{ 7, 11, 19, 43, 67, 163\}$

• $n < p-1$

for both primes $x_1=6k-1$ and $x_2=6k+1$:

$n²+n+p=6k-1[+2]$

$\delta= 1+24k-4[+8]-4p = 24k-4[+8]-H$ where $H$ is Heegner number

the valid solution of n is $\frac{\sqrt{\delta}-1}{2}$

this condition must be verified in case of existence

$n<p-1$

• $p>\sqrt{6k+1}$

twin primes are the case when $\delta$ is integer it means

• $24k-4[+8]-H$ is square where $\frac{H+1}{4}=p$ verifies the topper condition and $H$ is Heeger number.

as been stick in this polynomial , we can go until upper bound of primes with $p=41$

• algorithm works for all primes $x<41²= 1681$

---

as conclusion :

• $H>4\sqrt{6k\pm1}-1$

• $24k-4[+8]-H$ is square.

---

Numerical Application:

(17,19) , k=3

$\delta= 1+24*3-4[+8]-4p = 68[+8]-H$

$p>\sqrt{19}>4$

$H=4p-1>15$

$68-(H=19)$ i a square , and $68+8-(H=67)$ is square that means (17,19) is twin prime

Note

• we can still use other polynomials cited upward if the pimes searched for are $> 1681$