Twin Primes

April 17, 2012

Pairs of prime numbers that differ by two are known as twin primes: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), …. Sometimes the list is given by the lowest number in the pair (A001359: 3, 5, 11, 17, 29, 41, 59, 71, …), sometimes by the highest number in the pair (A006512: 5, 7, 13, 19, 31, 43, 61, 73, …), sometimes by the number in between (A014574: 4, 6, 12, 18, 30, 42, 60, 72, …), and sometimes just as a list of primes (A001097: 3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43, 59, 61, 71, 73, …). All twin primes have the form 6k±1.

It is simple and fast to compute the twin primes less than n by a variant of the Sieve of Eratosthenes. The sieving primes are the primes less than the square root of n, excluding 2 and 3 which are not of the form 6k±1. In the first step, the primes of the form 6k−1 are sieved; first make a bitarray for the numbers 5, 11, 17, 23, 29, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the second step, the primes of the form 6k+1 are sieved; first make a bitarray for the numbers 7, 13, 19, 25, 31, …, then, for each sieving prime p, find the smallest multiple of the prime in the list, strike it off the list, and strike each pth number off the list as well. In the third step, sweep through the pair of bitarrays and collect twin primes for each remaining pair of corresponding bitarray elements.

The smallest multiple of a prime p of the form 6k−1 is the modular inverse of 6 mod p; the smallest multiple of a prime p of the form 6k+1 is the modular inverse of −6 mod p. Be sure not to strike the prime p. We discussed the modular inverse in a previous exercise.

An alternative method to compute twin primes is to use the normal Sieve of Eratosthenes to compute the primes less than n, then sweep through the list comparing each prime to its successor. But the algorithm given above is faster, about twice as fast, because the two bitarrays are shorter than the single bitarray of the normal Sieve of Eratosthenes.

Your task is to write a function that finds the twin primes less than a given input n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

7 Responses to “Twin Primes”

  1. ardnew said

    Perl solution, lots of code

    use strict;
    use warnings;
    
    our $BITS = 32;
    
    # checks if the bit representing parameter n is set
    sub get($$)
    {
      my ($p, $n) = @_;  
      return 0 unless $n & 1;
      return 1 if $n == 2;
      $n >>= 1; # every bit represents an odd integer  
      return $$p[int($n / $BITS)] >> $n % $BITS & 1;
    }
    
    # sets the bit representing parameter n to b
    sub set($$$)
    {
      my ($p, $n, $b) = @_;  
      return unless $n & 1;
      $n >>= 1; # every bit represents an odd integer  
      my ($i, $o) = (int($n / $BITS), $n % $BITS);
      $$p[$i] &= ~(1 << $o);
      $$p[$i] |= !!$b << $o;
    }
    
    # computes the modular inverse
    sub mod_inverse($$) 
    { 
      my $m;
      my ($a, $b, $x, $y, $n) = ((shift) % ($m = shift), $m, 1, 0);
      
      while (0 != $a) 
      { 
        $n = int($b / $a);
        ($a, $b, $x, $y) = ($b - $n * $a, $a, $y - $n * $x, $x); 
      } 
      return $y % $m; 
    } 
    
    #
    # Our primes/sieve table is represented by a list P[] of
    # 32-bit integers. 
    # 
    # We map each natural number K to the bit table P[][] using:
    #
    #     K := 0, K is even
    #     K := P[ K / 64 ][ K (mod 64) ], K is odd
    #
    # This mapping has the advantage of only needing to keep
    # a record of the odd integers, reducing required memory.
    #
    # The list returned is the midpoints of the twins
    #
    sub sieve($)
    {
      my ($n, @a, @b) = shift;  
      
      my $m = sqrt $n;
      my @pairs = (4);
      
      # initialize the bit tables
      (push @a, 0), (push @b, 0) 
        foreach (0 .. ($n >> 1) / $BITS);
      
      # set all our numbers of the form 6k +/- 1
      map { set(\@a, 6 * $_ - 1, 1) } 1 .. ($n + 1) / 6;
      map { set(\@b, 6 * $_ + 1, 1) } 1 .. ($n - 1) / 6;
      
      # perform the sieve
      for (my $i = 3; $i < $m; $i += 2)
      {
        my ($r, $s) = (mod_inverse( 6, $i), 
                       mod_inverse(-6, $i));
                       
        set(\@a, $r, 0) unless get(\@a, $r);
        set(\@b, $s, 0) unless get(\@b, $s);
        
        my $k = $i + $i;
        
        set(\@a, $k, 0), set(\@b, $k, 0), $k += $i 
          while $k < $n;
      }
      
      # align the bits for easy matching
      $_ <<= 1 foreach @a;
      
      # if bits are set in corresponding positions,
      # add the midpoint to our list
      get(\@a, $_) and get(\@b, $_) and 
        push @pairs, $_ - 1 foreach 1 .. $n;
    
      return @pairs;  
    }
    
    0+@ARGV and print join ' ', sieve($ARGV[0]) or 
      die "\nusage:\n\t$0 <upper limit>\n\n";
    
  2. mrjbq7 said

    Solved using Factor.

    : twin-primes-upto ( n — seq )
    primes-upto 2 <clumps> [ first2 - 2 = not ] filter ;

    http://re-factor.blogspot.com/2012/04/twin-primes.html

  3. sibendu dey said

    #include
    #include

    int primecheck(int);
    void twinprime(int);

    void main() {
    int number;
    clrscr();
    printf(“Enter the MAximum number\n”);
    scanf(“%d”,&number);
    twinprime(number);
    printf(“\nThank You!!”);
    getch();
    }
    int primecheck(int prime) {
    int i,flag=1;
    for(i=2;i<=(prime/2);i++) {
    if(prime%i==0) {
    flag=0;
    return flag;
    }
    }
    return flag;
    }

    void twinprime(int max) {
    int i,j;
    for(i=2;i<=(max-2);i++) {
    if(primecheck(i)==1) {
    if(primecheck(i+2)==1) {
    printf("Twin primes are :%d %d\n",i,i+2);
    }
    }
    }
    }

  4. Dreddy said

    Sorry, at work, so syntax might be appalling but off the top of my head I thought something like this idea work:
    (warning may contain java-ish-ness)

    int[] primeArray;

    //find the primes less than N and by checking the usual does it divide by anything except 1 and itself, then add these to an array
    for(int i = 3; i < n; i++){
    int countOfDivisions = 0;
    for(t = 2; t < i – 1; t++){
    if((i.toNum() % t.toNum()) == 0){ //convert to something with decimals and mod that bad boy
    countOfDivisions++;
    }
    }
    if(countOfDivs == 0)
    int.push(i); //add, push, attach, whatever
    }

    //cycle through the array of primes found and print out the pairs, length – 2 to stay in array but check the position after i
    for(int i = 0; i < primeArray.length – 2; i++){
    if(primeArray[i + 1] – primeArray[i] == 2){
    System.out.println(primeArray[i] + ", " + primeArray[i + 1]);
    }
    }

  5. ardnew said

    I don’t mean to be a prude, but all other solutions posted on here completely disregard the proposed algorithm in the exercise description. Instead, they are either filtering the standard prime sieve, or repeatedly doing trial division. Both of these methods are kinda missing the point..

  6. Here’s my solution in Python:

    def twinPrimes(n):
    #list odd numbers
    odd = []
    a = 3
    while a <= n:
    odd.append(a)
    a = a + 2

    #list prime numbers via sieve of eratosthenes
    for p in odd:
    q = 2*p
    while p <= odd[-1]:
    p = p + q
    if p in odd:
    odd.remove(p)

    #odd now contains all prime numbers less than or equal to n
    for i in odd:
    if i + 2 in odd:
    print i, i + 2

  7. Guys, can somebody tell me how to properly insert code here. Thanks! :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: