List all primes p below 10000 such that every permutation of p's digits is a prime (e.g. 2, 37, 199).
Any conjectures?

Of course the single-digit primes, 2, 3, 5 and 7, fit the criterion. The program listed below finds all the remainder, showing only one prime for each set of digits that work--the lowest prime in the group. The results are:

 11
 13
 17
 37
 79
 113
 199
 337
 
No 4-digit primes are found, nor any 5-, 6- or 7-digit numbers for that matter, in a variant of the program, so one can conjecture that these constitute the complete list. However Sloane A003459 lists repunit primes 1111111111111111111, 11111111111111111111111, as obviously fitting the criterion, but of course permutation of such primes is trivial. Sloane also mentions that "The next terms are R(317), R(1031), R(49081), where R(n) is (10^n-1)/9." This Sloane sequence is the list of all the numbers (i.e., permutations of the digits), rather than the reduced list I show to avoid repeating sets of digits.

 
The program is:

   10     p=7
   20     while p<10000
   30       p=nxtprm(p)
   40       ps=cutspc(str(p))
   50       good=1
   60       for i=1 to len(ps)
   70        if instr("1379",mid(ps,i,1))=0 then good=0
   72        if i>1 then if mid(ps,i,1)<mid(ps,i-1,1) then good=0
   80       next
   90       if good then
  100        :h=ps
  110        :repeat
  120          :pt=val(ps)
  130          :if prmdiv(pt)<pt then good=0:endif
  140          :gosub *permute(&ps)
  150        :until ps=h
  160        :if good then print p:endif
  170       :endif
  180     wend
  190     end

The permute subroutine is shown elsewhere on this site.

Posted by Charlie on 2012-06-17 16:34:33