7
$\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 ?

|cite|improve this question
$\endgroup$
  • $\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$ – Gregory Grant Apr 7 '15 at 1:08
  • $\begingroup$ Only testing 6k+1 when 6k-1 is a prime is probably too obvious :) $\endgroup$ – Maarten Bodewes Apr 7 '15 at 1:11
  • $\begingroup$ or testin 6k-1 if the other is prime $\endgroup$ – Abdou Abdou Apr 7 '15 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$ – Jean-Claude Arbaut Apr 7 '15 at 22:47
  • 2
    $\begingroup$ "As we know each prime number...": Each prime number greater than three. $\endgroup$ – TonyK Apr 7 '15 at 23:07
3
$\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

|cite|improve this answer
$\endgroup$
  • 6
    $\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 '15 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$ – michaelmross Jun 16 '15 at 19:19
  • $\begingroup$ The short answer is that you are testing primality of their product, which should be about 2x faster. $\endgroup$ – Oscar Smith Aug 22 '16 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$ – michaelmross Aug 22 '16 at 16:43
  • $\begingroup$ Incidentally, products ending in 3 are twice as frequent as 9 because: 1*3 =3 7*9 =3 9*1 =9 $\endgroup$ – michaelmross Aug 22 '16 at 17:05
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$
|cite|improve this answer
$\endgroup$
  • 2
    $\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$ – Steven Stadnicki Apr 24 '15 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 '15 at 1:35
  • 1
    $\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$ – Steven Stadnicki Apr 24 '15 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 '15 at 11:42
1
$\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.

|cite|improve this answer
$\endgroup$
0
$\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.

|cite|improve this answer
$\endgroup$
  • 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$ – Nicolas Bourbaki Apr 7 '15 at 1:25
  • $\begingroup$ @Nicolas Bourbaki well you are right, I mean not trivial algorithm. $\endgroup$ – iadvd Apr 7 '15 at 1:28
  • $\begingroup$ updated my answer... $\endgroup$ – iadvd Apr 7 '15 at 1:29

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.