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
contains the digit 6 (I have a proof)"

Solution

Jim R. Howell sent (14/06/99) the following explanation:
"Consider any 9-digit number with distinct digits.  If this number does not contain the digit "6", then it is the other 9 digits (0,1,2,3,4,5,7,8,9) in some order.  But the sum of these digits is 39, so this 9-digit number is divisible by 3.  Therefore, if "6" is missing, the number cannot be prime. A similar argument can be used to show that these 9-digit primes also contain the digits 0, 3, and 9."

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."