Permutable Primes and Compatible Primes

This post is about an open problems column by Gasarch-Gezalyn-Patrick so they can be considered co-authors on this post. The column is here.

Known: A permutable prime is a prime so that, no matter how you permute the digits, you get a prime.

The first 22 of them are: 

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991.

11 might seem like a silly example. However, all of the known  ones past 991 are just all 1's. Let \(R_n\) be the base 10 number which is represented by n 1's. 

The next three permutable primes are \(R_{23}\), \(R_{317}\), \(R_{1031}\). 

Those are all of the permutable primes that are known. The 2  conjecture is that there are 

(1) there are an infinite number of them

(2)  all those past 991 are of the form \(R_n\). 

There is more information and more conjectures about them in the open problems col pointed to above. 

I know of three online papers on permutable primes, see my website of them here.

New: A number n is a k-compatible (henceforth k-comp) prime if there are k permutations of n that are prime but not k+1 such permutations.

Examples:

a) 103 is 3-comp: 013, 031, 103 are  prime BUT 130, 310,301 are NOT prime.

b) 97 is 2-comp: 79 and 97 are prime and there are no other perms of 97.

c) 41 is 1-comp: 41 is prime BUT 14 is NOT prime. 

We have some (though not much) empirical data that suggests the following. Fix L, the length of numbers being considered. If you look at L-length primes that are 1-comp, 2-comp, etc the number of them will (with some exceptions)  first increase then (with some exceptions) decrease, though past k=L/2 (actually smaller) the are no L-length, k-comp primes. 

For rigorous conjectures and more information  see the paper pointed to above.