Given a number, does there exist a rearrangement of it's digit such that it becomes a prime?

Question

Question and the examples

Examples: $n=16$, then we can swap $6$ and $1$ to get a prime $61$

$n=92$ , we can swap the digits to get the prime 29

What is the sufficient criteria for there to exist a rearrangement of a number's digit such that number becomes a prime? It may be quickly noted that numbers with all digits even are immediately disqualified.

---

A way to find total number of primes from permutation of a number $n$'s digits

Note: After googling, I found this method was just Sieve of Eratosthenes

If I have a number of length $n$, then I found an algorithm to find number of prime permutation of it's digits. I remove the permutations which are divisible by any number $k<n$ till I reach $n$.

For example if I have 12345, I have the set of numbers $\{1,2,3,4 ,5 \}$ for a total of 5! permutations, from which first I remove the numbers divisible by two, then three , then four, finally I add back the numbers divisible by two and four.

Related topics

There are the permutable primes, which are primes which stay prime independent of shuffling of digits. It is clear that this is a subset of the kind of numbers which satisfy the criteria in the question.

Answer 1

For some numbers, there are a few more clever obstructions. Base $10$ has the property that

a number is a multiple of $3$ if and only if the sum of its digits is a multiple of $3$.

So, the permutation of digits of any number that is a multiple of $3$ is disqualified from being prime.

There are a few other examples that fail: if a number has very few even digits, like $22\dots 212\dots 2$ for a lot of twos, there aren't that many ways to rearrange the digits so that the number isn't automatically disqualified from being prime due to being even (you can do the same with multiples of $5$, if you like). So, as long as $22\dots221$ isn't prime (and there's no reason to think it should be), there's no way to reorder its digits to make it prime.

The prime number theorem (very, very roughly) says that a number with $d$ digits has a "probability" of $\frac1{d\ln10}$ of being prime. (There are quotes around probability because this really doesn't make sense unless you're actually choosing a random number from a large enough interval; for more information on this notion, see this question). So, as long as the number of ways to reorder the digits of your number in a "not obviously not prime" way is a good bit larger than $d$, you should expect at least one of those reorderings to be prime. This is not a mathematically rigorous application of the prime number theorem, however, so it may be possible to find lots of numbers with many reorderings all of which are composite. This is likely not provable using current techniques.