Permutable Primes

Permutable primes are a fascinating subset of prime numbers characterized by their unique property: any permutation of their digits results in another prime number. This intriguing feature makes them a subject of interest in number theory, as they exhibit a form of symmetry and resilience against the typical randomness of prime distribution.

The concept of permutable primes is closely tied to the idea of digit rearrangement. For a number to be considered a permutable prime, every possible rearrangement of its digits must also yield a prime number. This requirement imposes a stringent condition, making permutable primes exceedingly rare, especially as the number of digits increases.

One of the simplest examples of a permutable prime is the number 13. Its only permutation, 31, is also a prime number. As the number of digits increases, finding permutable primes becomes significantly more challenging due to the combinatorial explosion of possible permutations and the decreasing likelihood that all permutations remain prime.

code.js
1function isPermutablePrime(n) {
2  const digits = n.toString().split('');
3  const permutations = getPermutations(digits);
4  return permutations.every((perm) => isPrime(parseInt(perm.join(''))));
5}
6
7function getPermutations(digits) {
8  return digits.length === 1 ? [digits] : digits.flatMap((digit, index) => getPermutations(digits.slice(0, index).concat(digits.slice(index + 1))).map(perm => [digit].concat(perm)));
9}
10
11function isPrime(n) {
12  if (n <= 1) return false;
13  if (n <= 3) return true;
14  if (n % 2 === 0 || n % 3 === 0) return false;
15  for (let i = 5; i * i <= n; i += 6) {
16    if (n % i === 0 || n % (i + 2) === 0) return false;
17  }
18  return true;
19}

Theorem

Let be a permutable prime in base , formed using digits and , where the number has length . Let be a prime such that . Assume is a primitive root modulo , , and . Under these conditions, must be divisible by .

Proof

Because is a primitive root modulo , the powers of cycle through all nonzero residues mod . That is, are all distinct .

Now consider the numbers of length , where only one digit is and all others are , in each of the digit positions: Since is a primitive root mod , the positions of in these numbers make their values mod all distinct.

Thus, these numbers are distinct mod . They form a complete residue system modulo , meaning one of them is congruent to 0, and the others to . That is, at least one of these numbers is divisible by .

But since all permutations of the digits must be prime, none can be divisible by . The only exception is the repdigit with all digits equal to , i.e., . Therefore the repdigit must be divisible by , but since , this is only possible if the repunit is divisible by .

Since is a primitive root mod , the multiplicative order of is , which implies:

Therefore if a base is a primitive root modulo a prime , and and , then any permutable prime formed from digits of length must satisfy:

This constraint rapidly limits the values can take as increases. Consequently, non-repunit permutable primes of large length are very rare or impossible under these conditions.