Reflective and Cyclic Sets of Primes

If the binary representations of the first several primes are reversed, 
the resulting number is also irreducible (i.e., either a prime or 1).  
This was pointed out by John Rickert, who cited the following 
reflective pairs of primes

                           reverse prime
      prime                (or unit)
        2     10        01   1       (or 010 to 010)
        3     11        11   3
        5    101       101   5
        7    111       111   7
        11  1011      1101  13
        13  1101      1011  11
        17 10001     10001  17

The first prime whose binary reversal has a proper factorization is
19 = 10011, which gives 11001=25.  Still, of the primes less than
2048, more than half of them have prime reflective partners.

I suspect the proportion of such primes becomes arbitrarily small 
as we go to larger and larger numbers.  To illustrate, here's a 
little table showing the number of such primes less than x for 
various values of x:

                              number of primes < x
            total number      that give primes under
      x     of primes < x     binary reversal         ratio
 --------   -------------    ---------------------     -------
      100          25               21                 0.8400
     1000         168              102                 0.6071
    10000        1229              509                 0.4141
   100000        9592             3054                 0.3184
  1000000       78498            20054                 0.2555
 10000000      664579           141772                 0.2133

I would expect that the fraction of primes whose reflective pairs
are also primes is roughly what would be expected based on a random
selection of an odd number with the correct number of binary digits
for each prime.  Thus it becomes increasingly less likely as the
density of primes (slowly) decreases.  Also, there are presumably 
infinitely many such prime pairs, although I don't know how to 
prove it.

One interesting approach to this problem might be based on interpreting
the binary representations as polynomials with reciprocal roots, 
as discussed in The Fundamental Theorem For Palindromic Polynomials.

By the way, here's some C code for counting reflective pairs:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
unsigned long ic,d,nmax, nn, n, i, imax, mm, kk, aa[30];
unsigned long ictot,ptot;
main ()
{
  nmax=1000;
  for(nn=3;nn<=nmax;nn=nn+2)
  {
    ic=0;for(d=3;d<sqrt(nn+1);d=d+2)if(nn%d==0)ic=1;
    if(ic==0)
    {
      for(i=0;i<31;i++)aa[i]=0;
      n=nn;i=0;
      while(n>0){aa[i]=n%2;n=(n-aa[i])/2;i++;}imax=i-1;
      mm=0;for(i=0;i<=imax;i++)mm=2*mm+aa[i];
      ic=0;for(d=3;d<sqrt(mm+1);d=d+2)if(mm%d==0)ic=1;
      ictot=ictot+ic; ptot=ptot+1;
      printf(" %lu %lu %lu %lu %lu \n",ptot,nn,mm,ic,ictot);
    }
  }
}

On a slightly related point, we can also consider "complete cyclic 
sets of primes", i.e., primes whose base-b expansions are primes
under all the rotations of their digits.  Obviously there are none 
in the base 2 other than repunits, i.e., primes of the form 2^p - 1.
However, for any higher base there exist complete cyclical prime 
sets.  Focusing on the base 10, some trivial examples of two-digit 
cyclic pairs of primes are

               13       37       17       79
               31       73       71       97

For slightly less trivial examples, we have the three-digit cyclical 
prime sets

             113       197       199      337
             311       719       919      733
             131       971       991      373


Among four-digit decimal numbers the only cyclic sets of primes are

                   1193          3779
                   3119          9377
                   9311          7937
                   1931          7793

Likewise among the five-digit decimal numbers we have only the sets

                  11939         19937
                  91193         71993
                  39119         37199
                  93911         93719
                  19391         99371

Finally, among six-digit decimal numbers the only cyclic sets of
primes are
                 193939        199933
                 919393        319993
                 391939        331999
                 939193        933199
                 393919        993319
                 939391        999331

There are no complete cyclic sets of decimal primes with 7 or 8 digits,
and perhaps not with any greater number of digits.  

Of course, we can also find cyclic sets of primes in other bases.  For
example, in the base 7 we have the set

                        11515
                        51151
                        15115
                        51511
                        15151

Also, whenever a repunit is a prime, it gives a degenerate cyclic set,
such as the number 1111111 in the base 3 (which equals the prime 1093 
in decimal).

Return to MathPages Main Menu
Сайт управляется системой uCoz