Tell me more ×
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.
up vote 4 down vote favorite

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 at 3:48
well basically something other than a brute force – frogeyedpeas Jan 15 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 at 4:07

4 Answers

up vote 9 down vote

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 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 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 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 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 at 4:13
show 3 more comments
up vote 1 down vote

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 at 3:48
up vote 1 down vote

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 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 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 at 16:23
up vote 0 down vote

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 at 3:59
*Can all the prime numbers less than a number N be determined in polynomial time? – frogeyedpeas Jan 15 at 4:02
Oh definitely. Look up the various sieves. – Greg Ros Jan 15 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 at 4:08
ahhh so it still is a slow process to find them – frogeyedpeas Jan 15 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.