### On the determination of permutable primes

#### by David Radcliffe

**Edit:** I have to retract this proof. It was pointed out to me that 10^k covers only 16 of the 17 congruence classes modulo 17, so the last step fails. The other steps are valid, and they show that a permutable prime greater than 991 must be a near-repdigit (all but one of the digits are equal) or a repunit.

A permutable prime (also called an absolute prime) is a prime number such that all of its digit permutations (in base 10) are prime. For example, 113 is a permutable prime, since each of the numbers 113, 131, and 311 are prime. Note that all permutable primes greater than 5 are composed of the digits 1, 3, 7, and 9. The following is a complete list of the permutable primes less than 1000.

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

A repunit prime is a prime number that contains only the digit 1. Every repunit prime is permutable, and it is conjectured (but not proved) that there exist infinitely many repunit primes. I will prove that the above list contains every permutable prime, with the exception of repunit primes greater than 11.

The proof is based on the following observation. If *N* and *m* are integers greater than 1 such that the digit permutations of *N* cover all congruence classes modulo *m*, then every number containing the digits of *N* (as a multiset) is composite. We can find a finite number of pairs (*N*, *m*) that will cover every case; however, the number of cases is too large to check by hand. The complete proof was generated by a Python script, and the output is available here.

The first step is to find all permutable primes less than 10^{6} by brute force search. We use the Miller-Rabin primality test (code is here). This is a probabilistic test, but we are not overly concerned with false positives, because we would run a separate deterministic test on any new candidate primes that were identified.

The second step is to verify that a permutable prime cannot contain all four of the digits 1, 3, 7, and 9, by showing that the permutations of 1379 cover all congruence classes modulo 7.

The third step is to verify that a permutable prime cannot contain exactly three of the four digits 1, 3, 7, and 9. There are two sub-cases: the number contains two digits that are repeated at least twice, or the number contains a digit that is repeated five or more times These sub-cases are denoted *aabbc* and *aaaaabc*, respectively. As in the previous case, we show that the permutations cover all congruence classes modulo 7. These two sub-cases cover all of the remaining possibilities, since we checked all numbers having fewer than seven digits in step 1.

The fourth step is to verify that a permutable prime cannot contain exactly two of the four digits 1, 3, 7, and 9, unless it is less than 10^{6}. There are two sub-cases: the number contains two digits that are repeated at least twice (such as 11133), or the number has all digits the same except for one (such as 11113). For the first sub-case, we consider permutations modulo 7 as before. Unfortunately, there is no proof of the second sub-case using modulo 7 arithmetic, so we must work harder.

Suppose that *N* is a positive integer with at least 17 digits, all of which are equal to *a*, except for the last digit which is equal to *b*. Then the following 17 numbers are digit permutations of *N*.

~~Since 10 is a primitive root modulo 17, these numbers cover all congruence classes. Therefore, ~~*N* cannot be a permutable prime.

~~It remains to check that there do not exist any permutable primes of the form ~~*aaa…ab* that have between 7 and 16 digits. We do this by checking each candidate with a Miller-Rabin primality test. This exhausts all of the possible cases, so the proof is complete.

Since 10 is a primitive root modulo 17, these numbers cover all congruence classes, except the one belonging to . Therefore, *N* cannot be a permutable prime unless , which happens when the number of digits of *N* is a multiple of 16.

I will explain the main idea with an example. If we permute the digits of 1379 and divide the resulting numbers by 7, we obtain all possible remainders (0 through 6). If a number ends in 1379, and we permute the last four digits, then we also obtain all possible remainders. Therefore, if N is any number containing the digits 1,3,7,9, then some permutation of the digits of N yields a number that is divisible by 7.

You could mend the proof, at least as a near-proof, in the following way:

In your retracted proof you showed (using modulo 17) that N cannot be a permutable prime unless the number of digits of N is a multiple of 16.

The same can be done with other Numbers that have 10 a a primitive root, i.e. with any number of the Integer sequence A001913 in the OEIS (with the exception of 7 in the case N is a near-repunit of 7)..

So the number of digits of N has to divisible by 16, 18, 22, 28, … (n-1), n being the largest member of A001913 less than N. which gives the least common multiple of these numbers. Using brute force to find primes with 10 a primitive root up to 439007, I found that the numbers of digits of N must have more than 5.74*10^16432 digits.

I tried a formal proof that such a method will show the number of digits of a non-repunit permutable prime has to be infinite, using safe numbers. But safe numbers are far more rare than I imagined: according to wiki they have a density close to twin primes, and according to mathworld the number of twin primes may even be finite!

Maybe you as a professional mathematician can find a formal proof using the above suggestions.

English is not my mother tongue