Mystery Of The Permutable Primes

Relevant wiki: Prime Numbers

The only permutations of a two digit number $ab$ is itself and $ba$ . So we are looking for all the 2 digit primes such that when we reverse the digits the new number is also prime.

Now any number of this form cannot have a $2,4,6,8,5$ in it since any number ending in these digits cannot be prime.

Then just going through an exhaustive count of all these primes and checking them we see that

$11, 13, 17, 31, 37, 71, 73, 79, 97$

are the only two digit permutable primes in base 10.

---

Here's a few fun observations :

• It's worth pointing out that it's still a mystery whether there are infinitely many permutable primes in any base system (as far as I know).

• Also, in Base 2 all the permutable primes must be of the form $111...11$ since if they have a $0$ digit, some permutation can put this as the last digit of a number and that would be divisible by 2! All of these numbers therefore must be of the form $2^n - 1$ and must be mersenne primes! It's still not known if there exist an infinite number of these (again, as far as I know)!

• The only permutable primes (in base 10) less that $100,000$ are

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

• Here's the wikipedia page on permutable primes for more info.

It also solvable by C