Prime permutations

Since any 3-digit numbers ending in an even digit or $5$ are not prime, we limit ourselves to the digits 1, 3, 7, 9. We can make four subsets: $\{1,3,7\}, \{1,3,9\}, \{1,7,9\}, \{3,7,9\}.$ We must check divisibility by primes up to 31.

For divisibility by 3, consider the sum of digits. For the four sets of digits, they are 11, 13, 17, 19, none of which are multiples of three.

For divisibility by 7, consider that $\overline{xyz}$ is a multiple of 7 iff $2x + 3y + z$ is. This simplifies even more if one of the digits is 7.

• Since $2\cdot 3 + 1 = 7$ , $371$ is a multiple of 7. This rules out the first set.

• Since $2\cdot 9 + 3\cdot 1 = 21$ is a mutiple of 7, so is $917$ . This rules out the third set.

• Since $2\cdot 9 + 3 = 21$ is a multiple of 7, so is $973$ . This rules out the fourth set.

The second set also has a multiple of 7 (931) but this may be harder to see. Note, however that $9 - 1 + 3 = 11$ , so that $913$ is a multiple of 11. Either way, we have excluded the second set.

Therefore there are no sets of three digits that satisfy the requirements.

Extensions: What if we work with four distinct digits? What if we allow two or more of the digits to be equal?

I have to be honest my solution is kind of ugly and involves some rigorous work but here it is anyways.

First off let's start by eliminating possibilities of digits. Obviously $a, b$ or $c$ cannot be even, nor can any of them be the digit $5$ . This leaves us with the possible digits $1,3,7$ and $9$ .

How many ways are there of choosing 3 digits/items in a list of 4? $4C3$ or 4 ways. The possible picks are $(1, 3, 7), (1, 7, 9), (1, 3, 9)$ or $(3, 7, 9)$ .

The only thing left to show is that at least one of the permutations of these three picks are not prime.

So I used a prime number database and found that for $(1, 3, 7)$ , $731$ was not prime. For $(1, 7, 9)$ , $791$ was not prime. For $(1, 3, 9)$ , $931$ was not prime and finally for $(3, 7, 9)$ , $793$ was not prime.

This means that no there do not exist any 3 distinct digits $a, b, c$ such that all 6 permutations $\overline{abc}, \overline{acb}, \overline{bac}, \overline{bca}, \overline{cab}$ and $\overline{cba}$ are all prime.

The reason I say it's not a nice solution is because in the worst case scenario you would have to end up checking if 24 numbers are prime or not prime.

No. From the list of all 3-digit prime numbers we eliminate all with repeating digits, all containing the even digits 02468, and all containing 5. We end up with 13 eligible primes made from 1379. Direct check gives us these lines:

137,173,317;

179,197,719,971;

139,193;

379,397,739,937.

None of these lines has 6 primes.

DIVISIBILITY BY 2?

• Any 3-digit integer ending in 0, 2, 4, 6, or 8 is divisible by 2, so ...
• ... we eliminate all even digits from consideration.

DIVISIBILITY BY 5?

• Any 3-digit integer ending in 5 is divisible by 5, so ...
• ... we eliminated from consideration.

REVISED QUESTION:

• Are there any three distinct digits out of the set {1, 3, 7, 9} such that all six permutations are prime numbers?

DIVISIBILITY BY 3?

• The sum of the four remaining digits (1+3+7+9) is equal to 20
• The only possible sums of three of these digits are 20-1, 20-3, 20-7 and 20-9.
• None of these, 19, 17, 13 or 11, are divisible by 3
• None of the 3 digits that can be made from 1, 3, 7 and 9 are divisible by 3.

FOUR SUBSETS TO CONSIDER!

• {1, 3, 7}
• {1, 3, 9}
• {1, 7, 9}
• {3, 7, 9}

DIVISIBLE BY 7?

A (relatively) simple check for divisibility of the number XYZ is to test the divisibility of XY - 2Z.

• XYZ is divisible by 7 if and only if XY - 2Z is also divisible by 7

Let's scan each subset to see if we can find one permutation that is divisible by this trick:

• 317? → 37 - 2 · 1 = 37 - 2 = 35 → 35 is divisible by 7 so 371 is divisible by 7
• 931? → 93 - 2 · 1 = 93 - 2 = 91 → 9 - 2 · 1 = 7 → 91 is divisible by 7, so 931 is divisible by 7
• 791? → 79 - 2 · 1 = 79 - 2 = 77 → 77 is divisible by 7 so 791 is divisible by 7
• 973? → 97 - 2 · 3 = 97 - 6 = 91 → 9 - 2 · 1 = 7 → 91 is divisible by 7, so 973 is divisible by 7

CONCLUSION

• We have eliminated every combination of three digits out of the set {1, 3, 7, 9}.
• There is no set of three digits in which every permutation is prime because ...
• ... every possible set of three digits includes at least one possible composite permutation.

ONE MORE TRICK? DIVISIBLE BY ELEVEN?

• A trick we can use with XYZ is to add the first and third digits and subtract the middle digit:

• XYZ is divisible by 11 if and only if X+Z-Y is divisible by 11

• 913? 9+3-1 = 11 → 11 is divisible by 11, so 913 is divisible by 11.

But we didn't need this final test, as we already proved it above. I just included it here because it's a neat little trick.

You can use Algebra to prove why these tricks work.

I dunno. Let's find out:

1

curl -s "http://primes.utm.edu/lists/small/1000.txt" | tail -n +5 | tr " " "\n" | perl -pe "s/^(\d\d)$/0\1/" | grep -Ph "^(1[^1]{2}|3[^3]{2}|7[^7]{2}|9[^9]{2})$" | grep -Ph "^\d1[^1]|\d3[^3]|\d7[^7]|\d9[^9]$" > tmp.txt; ots=`cat tmp.txt | grep -P "[137]{3}" | wc -l`; otn=`cat tmp.txt | grep -P "[139]{3}" | wc -l`; osn=`cat tmp.txt | grep -P "[179]{3}" | wc -l`; tsn=`cat tmp.txt | grep -P "[379]{3}" | wc -l`; if [[ `echo $ots$otn$osn$tsn | grep "6"` -eq 0 ]] then echo "Nope."; else echo "Yup."; fi; rm tmp.txt

Or more readably:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#!/bin/bash
# First grab source file and sanitize it a bit.
# We can safely ignore 0,2,4,5,8
curl -s "http://primes.utm.edu/lists/small/1000.txt" | tail -n +5 | tr " " "\n" | perl -pe "s/^(\d\d)$/0\1/" | grep -Ph "^(1[^1]{2}|3[^3]{2}|7[^7]{2}|9[^9]{2})$" | grep -Ph "^\d1[^1]|\d3[^3]|\d7[^7]|\d9[^9]$" > tmp.txt
# Search for all permutations:
ots=`cat tmp.txt | grep -P "[137]{3}" | wc -l`
otn=`cat tmp.txt | grep -P "[139]{3}" | wc -l`
osn=`cat tmp.txt | grep -P "[179]{3}" | wc -l`
tsn=`cat tmp.txt | grep -P "[379]{3}" | wc -l`
# Concatenate and search, since matches are at most 6, we are guaranteed 1 digit each
if [[ `echo $ots$otn$osn$tsn | grep "6"` -eq 0 ]] then
    echo "Nope."
else
    echo "Yup."
fi
rm tmp.txt

Which gives us:

1

Nope.

Mathematica

Select[Subsets[Range[0, 9], {3}],And@@PrimeQ[FromDigits/@Permutations@#]&] yields NO

I disagree. The problem never said that these numbers with three digits were in base 10. I feel pretty confidant that if we choose the right base, we'll be able to find a combination that works.