Problems & Puzzles: Puzzles Puzzle 59. Six and the nine digits primes (by Jud McCranie) "Prove that every 9digit prime (no leading zero)
that has distinct digits Solution Jim R. Howell sent
(14/06/99) the following explanation: Felice Russo sent a similar argument the 16/06/99. "Here's the story behind the puzzle, and its twisted path. I became interested in sequence A046732 (by our friend Enoch Haga)  primes with distinct digits whose reversal is also prime. There are obviously only a finite number of them, since any number with more than 10 digits can't have distinct digits. So I decided to find the largest member of the sequence, the total number of terms in the sequence, and the number with 1 digit, 2 digits, ... 10 digits. So I first wrote a program to use my existing file of prime numbers up to 4.29 billion. It seemed to be working, but to my surprise it didn't show any 10digit primes of this type < 4.29E9. So I checked my table of primes, and it seemed correct. I modified the program to not require that the prime be reversible  just that it had distinct digits. Again, it showed no primes of this type. Next I wrote a program to generate all primes between 10^9 and 10^10  and it showed no 10digit primes with distinct digits! I checked that program and I couldn't find any error. I still couldn't believe the result that there are no 10digit primes of this type, so I approached it from the other way. I wrote a program to generate all ndigit numbers with distinct digits and test them for primality. I checked the program on 9digit numbers, and it spit out plenty of these types of primes. Then I ran it for 10digit numbers, and again  no 10digit primes with distinct digits. So I started checking the program again. I was looking at a screenful of 9digit primes generated by the program and I noticed that every one of them had a "0"! I revised the program to test all 9digit primes with distinct digits, and sure enough  each one had a "0"! This is amazing, I thought. I checked 8digit primes with distinct digit, and some had a "0" while others didn't (as I would expect). I decided to check all digits on 9digit primes with distinct digits. They all have the digits 0, 3, 6, and 9! Now it finally dawned on me. The sum of the digits 0 through 9 is 45; 45 is divisible by 3; so any number using each of the digits once and only once is itself divisible by 3  hence not prime. And for 9digit numbers with distinct digits, if 0, 3, 6, or 9 is avoided, the sum of digits is divisible by 3 so the number itself is divisible by 3. So any 9digit prime with distinct digits must have 0, 3, 6, and 9; and there are no 10digit primes with distinct digits. I could have saved myself a lot of trouble and excitement if I had stopped to think when I first saw that there seemed to be no 10digit primes with distinct digits, but (naturally) I suspected an error in my program." 




