Problems & Puzzles: Puzzles
Puzzle 59.- Six and the nine digits primes (by Jud McCranie)
"Prove that every 9-digit prime (no leading zero)
that has distinct digits
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 10-digit 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 10-digit 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 10-digit primes of this type, so I approached it from the other way. I wrote a program to generate all n-digit numbers with distinct digits and test them for primality. I checked the program on 9-digit numbers, and it spit out plenty of these types of primes. Then I ran it for 10-digit numbers, and again - no 10-digit primes with distinct digits. So I started checking the program again. I was looking at a screenful of 9-digit primes generated by the program and I noticed that every one of them had a "0"!
I revised the program to test all 9-digit primes with distinct digits, and sure enough - each one had a "0"! This is amazing, I thought. I checked 8-digit primes with distinct digit, and some had a "0" while others didn't (as I would expect). I decided to check all digits on 9-digit 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 9-digit 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 9-digit prime with distinct digits must have 0, 3, 6, and 9; and there are no 10-digit 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 10-digit primes with distinct digits, but (naturally) I suspected an error in my program."