# Determining the next Twin Prime?

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?

• 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. – GregRos Jan 15 '13 at 4:07
• If you use simple trial division, at least you can reject numbers that are not twin primes quicker: To check whether p is prime, you would check that it is odd and not divisible by 3, 5, 7 etc. up to sqrt (p). To check whether p and p+2 are twin primes, you check they are odd, then you check whether (p+2) modulo x <= 2 and then (p+2) modulo x != 1, for x = 3, 5, 7 etc. So a pair will be rejected if a factor for one is found. Which will happen earlier on average than finding a factor of one number only. Only actual twin primes will not be examined faster. – gnasher729 May 14 '14 at 18:00

## 6 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).

• 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
• "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
• 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. – GregRos Jan 15 '13 at 4:13

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

• 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
• Let $x = x+2$ if $x$ isn't prime or $x = x+4$, prime can't be even ($x \neq 2$), and we checked $x+2$. ;) Here helpful could be Miller–Rabin primality test. – Tacet Nov 22 '14 at 16:17

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

• Thats intriguing that nobody has found one yet... – frogeyedpeas Jan 15 '13 at 3:48

Since $$\sigma_0(n−1) + \sigma_0(n+1)−4 \ge 0$$ with equality exactly when $n-1$ and $n+1$ are both primes, what about a generating function like \begin{align} \frac{4}{x-1} + \sum_{k=1}^\infty \frac{x^{k-1}(x^2\!+1)}{1-x^k} &= - 3 - 2x - x^2\! + x^3\! + 3x^5\! + 4x^7\! + x^8\! + 4x^{9}\! + x^{10}\! \\ &\hspace{3em} + 6x^{11}\! + 6x^{13}\! + 2x^{14}\! + 5x^{15}\! + 2x^{16}\! + 7x^{17}\! + 8x^{19}\! + \cdots, \end{align} where the set of missing exponents, $\{4,6,12,18,30,42,\dots\}$, is the set of twin prime separators? Does that suit your needs?

• Wait... hold up... how do we derive this? – Simply Beautiful Art Oct 8 '17 at 17:15
• The LHS is seriously miscomposed: summing over $n$ a quantity not depending on $n$? – Did Oct 9 '17 at 4:51
• If you sum over $x$, the sum should not involve $x$... – Wojowu Oct 9 '17 at 21:21
• Including $x=1$? – Did Oct 9 '17 at 21:25
• Suggestion (bis): Add this to the answer. – Did Oct 11 '17 at 15:47

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

• 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. – GregRos 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. – GregRos 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
• @robjohn That was intended to fall under the "Conjecturally" clause. – Erick Wong Jan 16 '13 at 16:34

There's a superfast method: Don't look for primes! Look for one tiny class of semiprimes. The product of all twin primes is an even perfect square minus 1. And since we're searching for semiprimes, a primality test is not required. Any factor (prime or not) less than the square root of X^2 - 1 eliminates the composite as a candidate. Furthermore, these factors are usually trivial - that is, they're found long before X.

Demonstration: http://www.naturalnumbers.org/TwinPrimeCalc.xlsm