Pandigital Prime Sets

Using all of the digits $1$ through $9$ and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set $\{2,5,47,89,631\}$, all of the elements belonging to it are prime.
How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

This problem involves some number theory and interesting combinatorics.

First, let’s acknowledge an important fact in number theory: a number is divisible by 3 if the sum of its digits is divisible by 3. Since here we’re using $1$ through $9$ exactly once, the sum of all those digits is $1+2+3+4+5+6+7+8+9 = 45$. $45$ is divisible by $3$, therefore if any formed number is going to be a prime, it cannot use all $9$ digits – because it would be divisible by $3$.

We can therefore only form primes with $1$ to $8$ digits. Let’s break it down:

**One-Digit Primes:** There are four single-digit primes: $2,3,5,$ and $7$.

**Two-Digit Primes:** We can consider all possible $2$ digits primes and eliminate the non-eligible ones. We find that there are $21-4-3=14$ of those conforming to the rule.

**Three-Digit Primes:** Testing all $3$ digits primes available, we see that only $25$ of them are suitable.

**Four-Digit Primes:** Testing all $4$ digits primes we have, we find out that we only have $35$ primes that meet our condition.

**Five-Digit Primes:** There are $126 – 25 – 55 = 46$ primes that are usable here.

**Six-Digit Primes:** We have $536 – 60 – 126 – 74 = 276$ primes.

**Seven-Digit Primes:** There are ${9 \choose 7} – 4 – 7 – 8 – 29 = 566$ primes that satisfy our property.

**Eight-Digit Primes:** There are $2$ primes here.

We will have to select a prime number of one category and keep going till we use all single digit numbers from $1$ through $9$. This has to be done in a systematic way not to over-count.

Also, if we have selected $k$ primes from our collection, the number of ways we can order them in our set is $k!$. Therefore, we will need to multiply the total by the factorial of how many primes we have picked.

All we have to do is find out all possible combinations as follows:

1) $2_{\text{digit}} * 4 * 1_{\text{digit}} * 2_{\text{digit}}*2_{\text{digit}}*2_{\text{digit}}*2_{\text{digit}} * 4! = 28224$

2) $3_{\text{digit}} * 3_{\text{digit}} * 3_{\text{digit}} * 3! = 22500$

3) $4_{\text{digit}} * 4_{\text{digit}} * 8_{\text{digit}} * 3! = 8820$

4) $5_{\text{digit}} * 5_{\text{digit}} * 3_{\text{digit}} * 3! = 16560$

5) $6_{\text{digit}} * 6_{\text{digit}} * 1_{\text{digit}} * 3! = 9936$

6) $7_{\text{digit}} * 1_{\text{digit}} * 2_{\text{digit}} * 3! = 20184$

7) $8_{\text{digit}} * 4_{\text{digit}} * 2! = 280$

Summing these seven cases yields a total of $105504$ sets.

More Answers: