6
$\begingroup$

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 ?

$\endgroup$
6
  • $\begingroup$ As far as I know, there's no known way of doing this that's computationally more efficient than what you call general number sweeping. $\endgroup$ Apr 7, 2015 at 1:08
  • 1
    $\begingroup$ Only testing 6k+1 when 6k-1 is a prime is probably too obvious :) $\endgroup$ Apr 7, 2015 at 1:11
  • $\begingroup$ or testin 6k-1 if the other is prime $\endgroup$ Apr 7, 2015 at 1:12
  • 1
    $\begingroup$ At least, you know it's feasible in polynomial time, since primality testing is itself polynomial (using AKS algorithm). But this does not help much. You may also have a look at the Twin Prime Search project. $\endgroup$ Apr 7, 2015 at 22:47
  • 2
    $\begingroup$ "As we know each prime number...": Each prime number greater than three. $\endgroup$
    – TonyK
    Apr 7, 2015 at 23:07

5 Answers 5

2
$\begingroup$

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

$\endgroup$
9
  • 8
    $\begingroup$ "Square root of the square root"- so basically the square root of the possible prime? How then is that better than trial division? $\endgroup$
    – adam W
    Apr 14, 2015 at 18:14
  • $\begingroup$ It's vastly better than trial div. There's no rational way to know which primes are twins without testing all of them. However, it's extremely simple to test their products because it's only the even perfect squares minus 1 - a tiny subset of numbers (and you only need to test up to the square root of the square root to dismiss it). $\endgroup$ Jun 16, 2015 at 19:19
  • $\begingroup$ The short answer is that you are testing primality of their product, which should be about 2x faster. $\endgroup$ Aug 22, 2016 at 14:36
  • $\begingroup$ Yes, that's all it is. You can also halve the number of $X^2-1$s to test because they all end in 3 or 9 (if product >35) for twins. $\endgroup$ Aug 22, 2016 at 16:43
  • 1
    $\begingroup$ Incidentally, products ending in 3 are twice as frequent as 9 because: 1*3 =3 7*9 =3 9*1 =9 $\endgroup$ Aug 22, 2016 at 17:05
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "Currently there is no such algorithm". I disagree, if I give you a pair (n,n+2), you can algorithmically test it for primeness by listing all numbers from 2 to n+1 and dividing both n and n+2, to see if they are divisible. So algorithms certainly exist. $\endgroup$ Apr 7, 2015 at 1:25
  • $\begingroup$ @Nicolas Bourbaki well you are right, I mean not trivial algorithm. $\endgroup$
    – iadvd
    Apr 7, 2015 at 1:28
  • $\begingroup$ updated my answer... $\endgroup$
    – iadvd
    Apr 7, 2015 at 1:29
-1
$\begingroup$

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$
$\endgroup$
4
  • 3
    $\begingroup$ 'billions of primes within a specific range' and 'algorithm works for all $p\lt 1681$' seem rather at odds with each other. Even the largest of the Heegner numbers will only give you primes up to about a million or so, and this certainly doesn't allow for checking of arbitrarily large numbers. $\endgroup$ Apr 24, 2015 at 0:44
  • $\begingroup$ @ Steven Stadnicki billions of them using other polynomials , cited above, euler is just an example , my method is still lower in complexity $\endgroup$
    – Abr001am
    Apr 24, 2015 at 1:35
  • 2
    $\begingroup$ None of the polynomials in the Wolfram link you cite offers more than a few dozen prime values (except for the 26-variable one that arises from the solution to Hilbert's 10th problem, and that one is wholly impractical). I've never heard of a prime-generating polynomial that works over ranges of billions of elements, and would be surprised if there were any known. I admit I can't make heads nor tails of your algorithm, but even given that I can't see any way that this is better abstractly than trial division. $\endgroup$ Apr 24, 2015 at 1:40
  • $\begingroup$ @StevenStadnicki "I can't see any way that this is better abstractly than trial division" of course you dont since you arent able to differenciate my answer 's head from its tail , this method isnt just useful for twins but all primes below 1681 . $\endgroup$
    – Abr001am
    Apr 24, 2015 at 11:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .