## 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:

Counting Block Combinations IIRed, Green or Blue Tiles

Red, Green, and Blue Tiles