Primes That Survive Every Shuffle

Take a number, write its digits in every possible order, and ask whether every one of those arrangements is prime.

For 13, the two arrangements are 13 and 31, and both are prime. Since nothing else can be made from a 1 and a 3, every arrangement passes the test, making 13 a permutable prime.

For 19 it is also two questions, and the second one ends it. Nineteen is prime, and 91 is 7 × 13. One composite arrangement is enough, so 19 is out despite being prime itself.

The number is always one of its own arrangements, which is why the laboratory lists it rather than starting after it. A number that is not prime fails at its own row, although a smaller composite arrangement may appear earlier because the list is sorted by value. The property being tested is about the whole set of arrangements, and the starting number belongs to that set.

Repeated digits are arranged once, not once per position. The digits of 199 give 199, 919 and 991, which is three arrangements rather than six, because swapping the two nines produces the same row of digits and counting it twice would be counting the same check twice.

The example chooser groups twenty starting values by what they demonstrate. Compare 113 with 131 to see that a different starting order gives the same arrangements, or compare 11 with 111 to see why having only one arrangement does not guarantee a prime. For a larger case, 123456 has 720 arrangements, all divisible by 3 because their digits always add to 21. In The survivors view, selecting any listed number takes you back to The shuffle to inspect its arrangements.

Run the search a little way and something odd happens to the alphabet. The survivors stop using most of the digits.

There is a reason, and it is worth finding before reading it. Take any number with two or more digits and pick a digit inside it. There is some rearrangement that puts that digit last. If the digit is 0, 2, 4, 6 or 8, the rearrangement is an even number of at least two digits, so it is composite. If the digit is 5, the rearrangement ends in 5 and is a multiple of five, so it is composite again.

So a number containing any of those six digits has an arrangement that is composite, and it cannot survive. What is left is 1, 3, 7 and 9. Four digits out of ten, and no computation was involved.

This is the moment the page is really about. The search has been finding things, and it looked as though the alphabet was one of its findings, and it was not: the alphabet is a theorem that would be true if nobody had ever run the search at all. The search confirms it over a range, the way a thermometer confirms that water boils. It is not where the fact comes from.

And having the right digits is not enough. 197 and 199 are both three digits from that alphabet, and 197 fails at 791 = 7 × 113 while 199 survives. Whatever separates them is not something the digits announce.

The sentence worth carrying away is this one.

A search over a range can confirm a theorem, and cannot produce one.

This page does both kinds of work and the difference is visible in the figures.

• Every permutable prime with more than one digit uses only 1, 3, 7 and 9. Proved, by the argument above, for every number there is.
• There are exactly twenty-two permutable primes below a million. Exhaustively checked over exactly that range, and it is a fact about that range.

The second one is the tempting one, because the list has such an obvious shape: nothing with four digits, nothing with five, nothing with six. It looks finished. The temptation is to read the empty rows as saying there are no more, and the search cannot say that, because the search stopped.

The repunits are where that goes wrong in the most direct way available. Nineteen ones in a row is a prime number. Every arrangement of nineteen ones is the same nineteen ones, so it is trivially a permutable prime, and it sits about twelve orders of magnitude above the largest bound this laboratory offers. The search that found twenty-two numbers had no chance of seeing it and no opinion about it.

There is a theorem here too, and it is somebody else's: a permutable prime with more than three digits and fewer than $6\times 10^{175}$ digits must be a repunit. Slinko reports the bound with attribution to Richert; this page does not reproduce the calculation. Both ends of that range are part of the statement. It does not say that every large permutable prime is a repunit; it says that every permutable prime in one enormous but bounded band of digit lengths is, and above the band the question is simply not addressed. With that theorem the empty rows stop being an absence and become an explanation. Without it they are just where the computer stopped.

Write $n$ in base ten with digits $d_1{d}_2\dots d_k$, and let $P(n)$ be the set of values of all distinct arrangements of those digits, $n$ among them. Call $n$ permutable when every element of $P(n)$ is prime.

1. $13$ is permutable, since $P(13)=\{13,31\}$ and both are prime. Proved.
2. $19$ is not, since $91=7\times 13\in P(19)$. Proved.
3. $197$ is not, since $791=7\times 113\in P(197)$, while $199$ is, since $P(199)=\{199,919,991\}$ and all three are prime. Proved.
4. If $n$ is permutable and $k\ge 2$, then every $d_i\in \{1,3,7,9\}$. Proved, below.
5. The permutable primes below $10^6$ are exactly $$2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733,919,991.$$ Exhaustively checked over exactly that range.
6. If $n$ is permutable and $3<k<6\times 10^{175}$, then $n=R_k=(10^k-1)/9$. Proved in the cited literature (Richert, as reported by Slinko), not reproduced here. The upper bound on $k$ is the theorem's own; nothing here covers a permutable prime wider than that.
7. $R_2$, $R_{19}$, $R_{23}$, $R_{317}$ and $R_{1031}$ are prime, and whether infinitely many $R_k$ are prime is open.

Statement 4 is what the page can prove for itself. Statement 5 is what it can check. Statement 7 is where both of them run out, and 6 is the bridge between them that belongs to somebody else.

Thirteen survives and nineteen does not. $P(13)=\{13,31\}$; both are prime, and the list is complete because two digits admit two arrangements. $P(19)=\{19,91\}$ and $91=7\times 13$. ∎

The alphabet is $\{1,3,7,9\}$. Let $n$ be permutable with $k\ge 2$ digits, and suppose some digit $d$ of $n$ lies in $\{0,2,4,5,6,8\}$. Choose the arrangement $m\in P(n)$ that places $d$ in the units position and any other digit in the leading position; such an arrangement exists because $k\ge 2$. Then $m\ge 10$, since it has $k\ge 2$ digits and a non-zero leading digit, which is available because $n$ is prime and so not every digit of $n$ is zero.

If $d$ is even then $2\mid m$, and if $d=5$ then $5\mid m$. Either way $m$ has a divisor strictly between $1$ and $m$, so $m$ is composite. But $m\in P(n)$ and $n$ is permutable, so $m$ is prime, a contradiction. Hence every digit of $n$ lies in $\{1,3,7,9\}$. ∎

Note what that argument does not use: no bound, no search, no primality test on anything. It is a statement about every number with two or more digits, produced by moving one digit.

Twenty-two below a million. Sieve to $10^6$; discard every prime containing a zero, by the argument above; group the rest by their digits sorted into order, so that one permutation class is one group; and declare a class permutable exactly when the group holds every arrangement the class has. Since $10^6$ is a power of ten, every arrangement of a $k$-digit number is a $k$-digit number and therefore inside the sieved range, so no class is decided on partial information. Counting the survivors gives the list in statement 5, in exact integer arithmetic. This proves statement 5 and nothing else. ∎

What is not proved here. Statement 6, which is cited, and statement 7, which is open. It is worth being explicit about why extending the search would not help with either. Every additional number checked removes one candidate from an infinite supply, and the four-digit rows were already empty at the bound the page reaches. A proof would have to be an argument about all $k$, and the one that exists for statement 6 is not reproduced here.

What this laboratory computes. Every arrangement of any number you type, up to eight digits, which is forty thousand arrangements at the ceiling and is refused above it rather than started. The survivors view sieves to the chosen bound, the largest being a million, and settles each permutation class by counting rather than by testing every arrangement separately. All of it is exact integer arithmetic, and the test suite checks the result against a second implementation that shares none of the machinery: every arrangement of every prime below a hundred thousand, generated as strings and tested one at a time.

What the repunit view does not do. It does not test $R_{317}$ or $R_{1031}$ for primality, and it does not show every known repunit prime. Those two are cited from the catalogue of known repunit primes, and the figure draws the first five of them: $R_{49081}$ and several beyond it are also known or established as probable primes, and are past what this page will build. $R_{19}$ and $R_{23}$ are checked in the test suite by a probable-prime test with fixed bases, which settles $R_{19}$ outright and is strong evidence rather than a proof for $R_{23}$. The bars in the figure are drawn at the numbers' real lengths and their digits are not printed, because a thousand and thirty-one characters is not something a figure can show a reader.

Change the base and the subject changes. In base two the only numbers with no zero digit are the repunits, so the permutable primes in base two are exactly the Mersenne primes, and the alphabet argument becomes trivial rather than interesting. That is the clearest sign that this is a property of how a number is written and not of the number: 31 is a permutable prime in base ten and in base two, and 37 is one in base ten and not in base two, and 31 and 37 have not changed.

Where the mathematics is still moving. Whether there are infinitely many repunit primes is open, and with the cited theorem in hand that is the same question as whether the list of permutable primes ends over the band of digit lengths the theorem covers. Repunit primes are known at 2, 19, 23, 317 and 1031 digits, and further ones at 49081, 86453, 109297 and 270343 digits are known or established as probable primes; the search has gone a long way past that without settling whether the list ends, which is a search result and settles nothing.

Read this next to Every Even Number, Two Primes. That page has a search that never fails and this one has a search that almost always does, and both end in the same place: a finite range checked completely, and a statement about all numbers that the checking cannot touch.