Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A really simple I question I guess. Is there an algorithm or method such that given an integer N there is a way to determine the next twin prime pair greater than N?

If yes then could you please explain it?

share|improve this question
1  
Perhaps you mean to ask if there exists an efficient algorithm for finding twin primes. Otherwise, a brute force search could be implemented. –  JavaMan Jan 15 '13 at 3:48
    
well basically something other than a brute force –  frogeyedpeas Jan 15 '13 at 3:56
    
There are established and extremely fast ways of finding primes. There just aren't any theoretically faster ways to find twin primes. In practice, you could improve an algorithm by a constant factor if you only searched for those. If you wanted just one prime, you might as well use brute force. Unless you wanted it extremely quickly, in which case you could use a divide and conquer approach that 'guesses' where the prime might be. –  Greg Ros Jan 15 '13 at 4:07
add comment

4 Answers

It isn't even known that there is always a twin prime pair greater than $N$ (so strictly speaking, there isn't an algorithm that is known to work).

share|improve this answer
    
Thats interesting, so if an algorithm is devised that works and it doesn't involve some extension of determine if P and P + 2 is prime then that would be considered an adequate proof of the twin prime conjecture? –  frogeyedpeas Jan 15 '13 at 3:51
    
There exists an algorithm. For there are two possibilities, (i) infinitely many twins or (ii) not. In case (i), there is an obvious algorithm. In case (ii), if we input a number $N$ that is too big, it says "You are SOL." We just don't happen to know which is the right algorithm. –  André Nicolas Jan 15 '13 at 3:53
    
I'm going to be logging out real soon but my question comes down to this: if I have an algorithm right now that always converges, –  frogeyedpeas Jan 15 '13 at 4:00
1  
"It is not feasible to construct a machine that will not find twin primes?" I'm pretty sure my toaster is a machine that will not find twin primes. –  Robert Israel Jan 15 '13 at 4:06
1  
Oh darn it you're right. I was so wrong in saying that. A toaster! Of course. I should have thought of that. I retract my statement. –  Greg Ros Jan 15 '13 at 4:13
show 3 more comments

Let $x=N+1$. If $x$ and $x+2$ are prime, you're done. If not, let $x=x+1$ and repeat. :-P

share|improve this answer
1  
Hmm... thats clever, but not exactly what i was thinking –  frogeyedpeas Jan 15 '13 at 3:47
    
lol, I didn't really think it was clever, but yeah what @Robert said. One of the great unsolved problems of math right now is the infinitude of twin primes... –  timidpueo Jan 15 '13 at 3:51
    
This works, but 10 minutes after you posted this answer, the OP commented that he desired something other than brute force. If there happen to be finitely many prime pairs, for a large enough $N$, this algorithm would behave like a calculator that was not built with the knowledge that division by $0$ is illegal. –  robjohn Jan 16 '13 at 16:23
    
Even better: if $N$ is even, let $x=N+1$, else $x=N+2$ and then always increment $x$ by 2 and keep primality test of the previous one. You can also keep track of multiple of three because at least one between x, x+2 and x+3 is a multiple of three... –  Mikaël Mayer Dec 21 '13 at 14:06
add comment

Nope. As far as I know there's no algorithm beyond sieveing for primes past $N$ until you find a twin pair.

share|improve this answer
    
Thats intriguing that nobody has found one yet... –  frogeyedpeas Jan 15 '13 at 3:48
add comment

I wouldn't be so quick to dismiss timidpueo's “algorithm” (although it could easily be made faster by replacing $N+1$ by $N+6$, among other tricks). Conjecturally, the average spacing between twin primes is $O(\log^2 N)$ and the worst-case spacing is $O(\log^3 N)$. So in practice, this is a polynomial time “algorithm” (even though it is not guaranteed to terminate, hence the quotes).

share|improve this answer
    
If the requirement is to find the next twin prime, though, you cannot rely on probabilistic algorithms. Though you could use this in order to increase the efficiency of the algorithm by employing a divide and conquer approach. –  Greg Ros Jan 15 '13 at 3:59
    
*Can all the prime numbers less than a number N be determined in polynomial time? –  frogeyedpeas Jan 15 '13 at 4:02
    
Oh definitely. Look up the various sieves. –  Greg Ros Jan 15 '13 at 4:06
    
Polynomial in $N$, yes, but "polynomial time" usually means polynomial in the size of the input (thus polynomial in $\log(N)$), and there are too many primes for that. –  Robert Israel Jan 15 '13 at 4:08
    
ahhh so it still is a slow process to find them –  frogeyedpeas Jan 15 '13 at 4:12
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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