Find the Nth pair of twin primes

Two prime numbers are defined as twin primes if they differ by two. For example, 3 and 5 are twin primes as are 29 and 31.

Write a program that finds the nth pair of twin primes (where n comes from STDIN) and prints them on STDOUT, separated by a comma and a space. This is code-golf, so the shortest code wins.

Sample input:

3


Sample output:

11, 13

• Wait... so the user will input the nth pair of twin primes, and you want us to output it? So, just echo back what the user inputs? ;-) – Iszi Jun 16 '14 at 8:29
• Hmm... That wording was a bit awkward! :P – Jwosty Jun 16 '14 at 16:30

main=putStrLn.(!!)[show n++", "++show(n+2)|n<-[2..],all((>0).rem n)[2..n-1],all((>0).rem(n+2))[2..n]].(+)(-1)=<<readLn


Brute-force all twin primes and prints the nth pair.

• Nice one! By seperating out the filtering function and using interact instead of putStrLn you can go even further and bring this down to 105: a#b=all((>0).rem a)[2..a-b];main=interact$(!!)[show n++", "++show(n+2)|n<-[2..],n#1,(n+2)#2].(+)(-1).read – Flonk Jun 16 '14 at 14:42 CJam, 29 26 bytes Y4]{{:)_{mp}/&!}g}q~*", "*  Try it online. Examples $ for i in {1..10}; do cjam twin-primes.cjam <<< $i; echo; done 3, 5 5, 7 11, 13 17, 19 29, 31 41, 43 59, 61 71, 73 101, 103 107, 109  How it works Y4] " Push [ 2 4 ]. "; { " "; { " "; :) " Increment each integer in the array. "; _ " Duplicate the array. "; {mp}/ " For each integer in the array, push 1 if it's prime and 0 otherwise. "; &! " Compute the logical NOT of the bitwise AND of the two previous integers. "; }g " If the result is non-zero, repeat the loop. "; }q~* " Do the above āNā times, where āNā is the integer read from STDIN. "; ", " " Join the array by comma and space. ";  Perl, 101 87 87 characters, building over aschepler's comment $n=pop;$r='^1$|^(11+?)\1+$';($t=1x$s)=~$r||"11t"=~$r||--$n||die"$s, ",$s+2,$/while++$s


$n=pop;$r=qr/^1$|^(11+?)\1+$/;(1x$s)!~$r&&(1x($s+2))!~$r&&++$i==$n&&say($s,", ",$s+2)&&exit while++$s  Usage: $ perl ./twin_primes.pl 10
107, 109


Explanation

$n = pop; # Pulls twin prime pair counter from @ARGV$r = qr/^1$|^(11+?)\1+$/; # The money line - a regex that verifies
# if a string of 1's has non-prime length

while ( ++$s ) { # Loop over integers # '&&' short-circuits (1 x$s    ) !~ $r # Negated regex match evaluates to true if$s is prime
&& (1 x ($s+2) ) !~$r   # Same for $s + 2 && ++$i == $n # Counter to control which pair to print && say($s, ", ", $s+2 ) # Print the line && exit # Terminate program }  The workings of the non-primality regex is explained in this SO question. • ..what is this? – seequ Jun 16 '14 at 19:50 • @TheRare : It utilizes a regex to check for the primeness of a number. – Zaid Jun 16 '14 at 19:52 • You just blew my mind. Have a +1. – seequ Jun 16 '14 at 19:54 • @TheRare : I added an explanation for why this works. I'm sure there is still room for improvement :) – Zaid Jun 16 '14 at 20:05 • Pretty much what I would have done. Have a few shaved characters: $n=pop;$r='^1$|^(11+?)\1+$';($t=1x$s)=~$r||"11$t"=~$r||--$n||exit say("$s, ",$s+2)while++$s – aschepler Jun 17 '14 at 0:18

C: 113

n,c,l;main(i){for(scanf("%d",&n),l=2;n;l=c==i?n-=i==l+2,i:l,i+=2)for(c=2;c<i&&i%c++;);printf("%d, %d\n",l-2,l);}


Sample run:

$for i in$(seq 1 10); do echo $i | ./twinprimes; done 3, 5 5, 7 11, 13 17, 19 29, 31 41, 43 59, 61 71, 73 101, 103 107, 109  Thanks for help from Dennis, bebe, and Alchymist. • You can save a few bytes by using scanf instead of command line arguments. Also, o=0 is unnecessary, since o is global. – Dennis Jun 16 '14 at 6:47 • main could hold a default int variable, incrementing c and i in between assignments and statements could shorten the code, the assignment of l could be taken back to the first for loop's third block so you would not need braces and using only one character of separator in printf could definitely make it more compact. – bebe Jun 16 '14 at 9:51 • Thanks, bebe! I noticed that I also had c<=i-1, which is just silly. – millinon Jun 16 '14 at 17:47 • I don't see a way to shave a byte by incrementing i in the l assignment expression, since the (new) value of i is used to decrement n. Any tips? – millinon Jun 16 '14 at 22:45 • if i remember correctly there is one place where you can increment i, but i belive its compiler dependent :( – bebe Jun 17 '14 at 6:42 CJam - 26 1e4,{mp},_2f-&qi(=_2+", "\  It works for primes smaller than 10000; you can replace 4 with a higher exponent for larger numbers (potentially up to 1020), but the program will get slower and will use more memory. Try it at http://cjam.aditsu.net/ Explanation: 1e4, creates the array [0 1 2 ... 9999] {mp}, selects only the prime numbers _2f- copies the array and subtracts 2 from each item & intersects the two arrays, thus finding the lower primes from each twin prime pair qi reads the input and converts to integer (= adjusts the index and gets the corresponding (lower) twin prime from the array _2+ copies the prime and adds 2 ", "\ puts the comma and space between the two primes Mathematica - 63 characters Print[#-2,", ",#]&@Nest[NestWhile[NextPrime,#,#2-#!=2&,2]&,1,n]  Notes This is in fact a rather straightforward implementation. Shortening resulted in almost no obfuscation. NextPrime is a builtin that finds the next prime after a number. NestWhile[NextPrime,#,#2-#1!=2&,2]& is an anonymous function that finds the larger prime of the next twin prime pair after a number. Nest applies this anonymous function n times. Print[#-2,", ",#]& is an anonymous function that prints to stdout according to the specifications. Sadly this alone takes up 18 characters of the 63 character solution. Example In[1]:= Do[ Print[#-2,", ",#]&@Nest[NestWhile[NextPrime,#,#2-#!=2&,2]&,1,n], {n, 1, 10} ] 3, 5 5, 7 11, 13 17, 19 29, 31 41, 43 59, 61 71, 73 101, 103 107, 109  Update: Two characters could be saved by reimplementing this CJam solution. However, this algorithm limits the maximum value of n. Just replace the Nest... part by Intersection[#,#-2][[5]]&@Prime@Range[999] • Where's your STDIN? :) – mfvonh Jun 20 '14 at 4:07 Javascript (E6) 92 96 Shorter and compliant - use spidermonkey shell to read stdin/write stdout (with comma and space). It finds the 10000th pair 1260989, 1260991 in under a minute on my PC Could be shorter using p[n]=o=n instead of p.push(o=n), so that the p array is sparse. But that's quite slower, and I'm not going to win for code length anyway. m=readline();for(n=3,o=p=[];m;n+=2)p.every(e=>n%e)&&(m-=n-o<3,p.push(o=n));print(o-2+', '+o)  To try in firefox console: m=prompt();for(n=3,o=p=[];m;n+=2)p.every(e=>n%e)&&(m-=n-o<3,p.push(o=n));alert(o-2+', '+o)  Ungolfed A function that found all first m twins (returns the largest value): T=m=>{ for (o=n=3, p=[2], t=[]; !t[m-1]; n+=2) p.every(e => n%e) && (n-o-2 ? 0 : t.push(n), p.push(o=n)) return t }  Example: console.log(T(50)) [5, 7, 13, 19, 31, 43, 61, 73, 103, 109, 139, 151, 181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 601, 619, 643, 661, 811, 823, 829, 859, 883, 1021, 1033, 1051, 1063, 1093, 1153, 1231, 1279, 1291, 1303, 1321, 1429, 1453, 1483, 1489] Just the last: L=m=>{ for (o=n=3,p=[2]; m; n+=2) p.every(e => n%e) && (m -= n-o==2, p.push(o=n)) return o }  Then, take that 2 lines and add IO m = prompt() for (o=n=3, p=[2]; m; n+=2) p.every(e => n%e) && (m -= n-o==2, p.push(o=n)) alert('o-2+', '+o)  J - 49 60 55 51 bytes I decided to go with a simple approach. Function t finds the next twin prime given a prime number as input (now this is included in the f function). Function f finds the nth twin prime. This also happens to be the first actual program I've written in J. f=:[:(":,', ',":@+&2)(4&p:(,{~-=2:)])^:_@>:^:(]2:)  Examples:  f 1 3, 5 f 2 5, 7 f 3 11, 13 f 4 17, 19 f 5 29, 31 f 100000 18409199, 18409201  Just for some eyebrowraises, have the ungolfed version. twin =: (4&p:)(($:@[)(,)@.(=(]+2:)))]
f    =: ((]-2:),])((0:{twin) ^: (](2:)))


Explanation:

f=:[:(":,', ',":@+&2)(4&p:(,{~-=2:)])^:_@>:^:(]2:)
(4&p:(,{~-=2:)])^:_@>:^:(]2:)
@>:^:(]2:)  main loop
^:(]2:)  Repeat n times, starting with value of 2
@>:          Add one to the current value and apply to the following function.
(4&p:(,{~-=2:)])^:_             Get the next twin prime
^:_             Recurse until there's no change
(,{~-=2:)                  If next prime - current value == 2, return current value, otherwise the next prime.
4&p:                           Get the next prime
(":,', ',":@+&2)                                Format the output and add 2 to the second value.
[:                                                Apply the twin prime to the formatter.

Basically, if n is 4, this creates a recursion tree like this:
let T be the recursion inside t
and numbers between rows the return values of according function
(t * n) 3
-> (t * 4) 3
-> t  t  t  t  3
17 11 5  3
-> (T  T) (T  T) T  T  3
17 13  11 7  5  3
-> 17

• This needs a bit more work to conform to the specifications: "prints them on STDOUT, separated by a comma and a space". Of course that's irrelevant to the algorithm, but it does increase the length of the program. – Szabolcs Jun 16 '14 at 17:05
• @Szabolcs better? – seequ Jun 16 '14 at 17:15
• Sure, +1. J is pretty cool. – Szabolcs Jun 16 '14 at 17:17
• @Szabolcs It really is. Although it reeeeeally bends my mind. Getting easier all the time though (this was the first program I wrote by hand). Also, thanks. – seequ Jun 16 '14 at 17:18

C#, 265

using System.Linq;class P{static void Main(string[] args){var i=int.Parse(args[0]);int f=0,c=0;for(int j=1;;j+=2){var b=(Enumerable.Range(1,j).Count(x=>j%x==0)==2);if(f==0 && b){f=j;continue;}if(b){c++;if(c==i){System.Console.WriteLine(f+","+j);break;}j-=2;}f=0;}}}

• +1 but you need to add one space after the comma when you print the mnumbers – Cristian Lupascu Jun 16 '14 at 15:38
• you can save two more chars: .Count(x=>j%x==0)==2) --> .Count(x=>j%x<1)<3) – Cristian Lupascu Jun 16 '14 at 18:35
• also, your class could be called P instead of Program and the parameter a instead of args. – Cristian Lupascu Jun 16 '14 at 19:32
• Won't compile as it is - you have an extra ) after the .Count(...)<3. You can also save a bit by changing var i=int.Parse(args[0]);int f=0,c=0; to int i=int.Parse(args[0]),f=0,c=0;. You can further save some by extracting the initialiser from the loop, so c=0;for(int j=1; => c=0,j=1;for(;. – Bob Jun 18 '14 at 0:22
• Also, a complete rewrite of the body of the for loop, plus using a fully qualified name rather than using System: using System.Linq;class P{static void Main(string[]args){int i=int.Parse(args[0]),f=0,c=0,j=1;for(;;j+=2)if(Enumerable.Range(1,j).Count(x=>j%x<1)>2)f=0;else if(f<1)f=j;else{if(++c==i){System.Console.WriteLine(f+", "+j);break;}j-=2;f=0;}}}, 238 chars. – Bob Jun 18 '14 at 0:34

Ruby 94

require'mathn'
n=gets.to_i
a=1
(a+=2;a.prime?&&(a+2).prime?&&n-=1)while n>0
$><<"#{a}, #{a+2}"  Online test: http://ideone.com/B2wxnG Perl, 100 95 $n=<>;$i=3;while($c<$n&&($l=$i++)){$i++until!grep{$i%$_<1}(2..$i-1);$c++if$i-$l<3}print"$l,$i"


Ungolfed:

$n = <>; # Read from STDIN$i = 3;           # Tiny hack because I know I don't need the number 2
while ($c<$n && ($l =$i++)) {   # $c counts the pairs,$l is the last prime
$i++ until ! grep {$i%$_<1} (2..$i-1);   # Increase $i until it's not divisible by anything$c++ if $i-$l < 3   # If $i and$l are twin primes, count it
}
print "$l,$i"    # That damned comma added a whole character to my code!


T-SQL (2008+): 344

Brute force a CTE to find primes, window function to count n, followed by a join to find the twin. Works in a second for outputs < 1,000, just under a minute for outputs < 10,000.

Golfed (SQLFiddle here):

WITH x(i) AS(SELECT 99 UNION ALL SELECT i-2
FROM x WHERE i>3),z AS(SELECT RANK()OVER(ORDER BY x.i)n,x.i
FROM x x LEFT JOIN x y ON x.i%y.i=0 AND y.i NOT IN(x.i,1)
WHERE y.i IS NULL)SELECT LTRIM(a)+', '+LTRIM(b)FROM(SELECT RANK()
OVER(ORDER BY x.i)n,x.i a,y.i b FROM z x,z y WHERE x.n=y.n-1
AND x.i=y.i-2) o WHERE n=3
OPTION(MAXRECURSION 0)


Legible:

WITH x(i) AS (
SELECT 99
UNION ALL
SELECT i-2
FROM x
WHERE i > 3
)
,z AS (
SELECT RANK()OVER(ORDER BY x.i)n,x.i
FROM x x
WHERE NOT EXISTS
(SELECT *
FROM x y
WHERE x.i%y.i = 0
AND y.i NOT IN (x.i,1)
)
)
SELECT LTRIM(a)+', '+LTRIM(b)
FROM (
SELECT RANK()OVER(ORDER BY x.i)n,x.i a, y.i b
FROM z x, z y
WHERE x.n = y.n+1
AND x.i = y.i+2
) o
WHERE n = 3
OPTION(MAXRECURSION 0)


GolfScript 46

~[1 3]\{\{))}%.{:x,{)x\%!},,2=}/*@\-.}do;', '*


Annotated code:

~                       # parse the input as an int
[1 3]                   # add the array [1, 3] on the stack
\                       # invert the items on the stack
{                       # begin loop
\                     # bring the array to the top of the stack
{))}%                 # add 2 to each of the numbers in the array
.{:x,{)x\%!},,2=}/    # check if numbers are prime (leaves a 0 or 1 for both numbers on the stack)
*                     # multiply the two 0/1 numbers (will only get 1 if both are 1)
@\-                   # subtract the result from the inital int
.                     # copy the new int value on the stack to be consumed by the 'do' loop
}do                     # repeat until the initial int was taken down to 0
# at this point the array contains the two numbers we're looking for
;                       # get rid of the 0 from the stack
', '*                   # format the output


PHP 5.4, 223

Not a smaller one, But one try from php.

$n=$argv[1];function i($k){for($i=2;$i<=(int)($k/2);$i++)if($k%$i==0)return 0;return 1;}function t($t){return (i($t) && i($t+2))?1:0;}$g=1;$d=0;do{if(t($g)==1){if($d<$n){$d++;}else{print_r([$g,$g+2]);break;}}$g++;}while(1);  C 309 Keeps getting next primes and store odd and even terms then checks if the difference is two. int main() { int n; scanf("%d",&n); int a=2,b=3,k=2,q; int odd=1; int p; if(n>0) { while(n) { k++; p=1; q=ceil(sqrt(k)); for(int i=2;i<=q;i++) { if(k%i==0) { p=0; break; } } if(p) { if(odd%2==0)a=k; else b=k; if(abs(a-b)==2)n--; odd++; } } } printf("%d %d\n",a,b); return 0; }  • Please not the square root! for (int i=2;i*i<=k;i++) – edc65 Jun 16 '14 at 20:01 R, 91 chars a=scan();n=1;p=5;while(n!=a){p=p+1;q=p-2;if(sum(!p%%2:p,!q%%2:q)<3)n=n+1};cat(q,p,sep=", ")  Nothing really fancy: a=scan() n=1 p=5 while(n!=a){ p=p+1 q=p-2 if(sum(!p%%2:p,!q%%2:q)<3) # Check that p and q are both primes by checking n=n+1 # the number of zeroes resulting from } # p modulo each integers 2 to p and same for q cat(q,p,sep=", ")  Usage: > a=scan();n=1;p=5;while(n!=a){p=p+1;q=p-2;if(sum(!p%%2:p,!q%%2:q)<3)n=n+1};cat(q,p,sep=", ") 1: 10 2: Read 1 item 107, 109  Japt, 23 19 bytes -4 bytes thanks to Shaggy @ĀµXĀ°j Ā©Ā°Xj}f [UU+2]  Run it online • 21 bytes – Shaggy Mar 1 '19 at 22:15 • 19 – Shaggy Mar 1 '19 at 22:25 • @Shaggy Nice! Thanks – Oliver Mar 1 '19 at 22:37 JavaScript (Node.js), 162 chars Reads from stdin, outputs to stdout, exits "early" for input <= 0. t=process.argv[2],c=0,l=1;if(t>0){for(i=0;;i++){p=!Array(i+1).join(1).match(/^1?$|^(11+?)\1+$/);if(p){if(i-2==l){if(c>=t-1){console.log(l+", "+i);break}c++}l=i}}}  Usage (script above saved as ntp.js): >for /l %x in (0, 1, 10) do node ntp.js %x >node ntp.js 0 >node ntp.js 1 3, 5 >node ntp.js 2 5, 7 >node ntp.js 3 11, 13 >node ntp.js 4 17, 19 >node ntp.js 5 29, 31 >node ntp.js 6 41, 43 >node ntp.js 7 59, 61 >node ntp.js 8 71, 73 >node ntp.js 9 101, 103 >node ntp.js 10 107, 109  AWK - 129 The file fsoe-pairs.awk: {n=2;N=1 for(;;){if(n in L){p=L[n];del L[n]}else{p=n if(n-N==2)if(!--$0){print N", "n;exit}N=n}P=p+n++
while(P in L)P+=p;L[P]=p}}


Running it:

$awk -f fsoe-pairs.awk 1 3, 5$ awk -f fsoe-pairs.awk
2
5, 7
\$ awk -f fsoe-pairs.awk
10
107, 109


(1st line after command is input, the 2nd one is output)

This is based on an own prime generator algorithm I call "floating sieve of erastosthenes" (until I find it described elswhere) which only stores the needed part of the sieve and the already calculated primes.

Python 2 (75)

c=input()
n=3
while c:n+=2;c-=all(n%i&~2for i in range(2,n-2))
print(n-2,n)


So what's going on here?

First, let's look at the expression all(n%i&~2for i in range(2,n-2)), which checks if (n-2,n) are a pair of twin primes.

The simpler expression all(n%i for i in range(2,n)) simply checks if n is prime by trying every divisor i in the range 2<=i<=n-1, and seeing if all remainders are nonzero. This all checks exactly this, since Python treats 0 as False and all other numbers as True.

Now, observe that (n-2)%i==0 exactly when n%i==2 for divisors i>2. So, we can perform the primality check on n and n-2 at the same time by checking the remainders for both 0 and 2. This could be done as all(n%i not in [0,2] for i in range(2,n-2)). We only try divisors in the range 2<=i<=n-3 for the sake of n-2, but this suffices for n as well since n-1 and n-2 can't be divisors unless n<=4. We will only try odd n starting from 5 to avoid this complication and that of the divisor i=2.

We golf the expression n%i not in [0,2] into n%i&~2, remembering that 0 is False and other numbers are True. The operator precedence (n%i)&(~2) is exactly what's needed. The bit-complement ~2 is ...11111101, so its bitwise and with a number zeroes-out the 2's binary place value. This gives 0 (i.e., False) only for 0 and 2, exactly what we want.

Phew! Now we have that the expression all(n%i&~2for i in range(2,n-2)) checks whether n is the upper number of a twin prime pair. What remains is to iterate over them until we see c of them, where c is the inputted number. We start with 5 and counting up by 2 to avoid divisor issues. We decrement c each time we encounter an n that works, stopping when c=0. Finally, we print the twin prime pair that we end with.

T-SQL(2012+),255 characters

A more compact T-SQL twin prime finder that also gets a little bit of a speed up.

with t(n)as(select 2+number from spt_values where type='p')select*from(select concat(b,', ',a),rank()over(order by a)from(select n,lag(n)over(order by n)from t where not exists(select*from t f where f.n<t.n and t.n%f.n=0))z(a,b)where a=b+2)r(s,k)where k=2


    with t(n)as(
select 2+number
from spt_values
where type='p'
)
select *
from(
select concat(b,', ',a),rank() over (order by a)
from(
select n, lag(n) over(order by n)

from t
where not exists(
select 1 from t f
where f.n<t.n and t.n%f.n=0)
) z(a,b)
where a=b+2
) r(s,k)
where k=2


The basic gist is we use the built in table of numbers (master..spt_values type='p') and alias that with a CTE as something short. We add 2 to remove the worry of pulling 0 or 1 trivial errors for our set, so now we have candidates of 2,2050.

Z the inner most query gets all primes from 2 to 2050, by filtering out any number n that is divisible by a number less than n. We then use a nifty T-SQL 2012 windowing function lag that lets us pull the previous result, so now Z's results a and b are the primes P[n] and P[n-1] respectively. The R query creates the output string, and filters out non-twin primes and also creates a sequence number for the output we call K. Finally the last query R allows us to filter and get the Kth twin prime by changing its variable.

Mathematica -- 71 bytes

n=Input[];
i=j=0;
While[j<n,i++;If[And@@PrimeQ[x={i,i+2}],j++]];Print@x
`