Mirror Primes

[gavinksong]

How many primes are the between 9 and 100 such that reversing the digits yields another prime?

This by itself is way too easy, so try to answer this using as little brute force as possible (or try to lower the upper bound as much as possible).

[gavinksong]

I have the prime numbers less than 100 memorized, but I could give an upper bound instead.

Because we are reversing digits and necessarily want prime numbers, we have to

leave out numbers that begin or end with a digit of 0, 2, 4, 5, 6, or 8.

Then, for the potential two-digit prime number, there are four choices (1, 3, 7, 9) for the first

digit, and also for the second digit.

That is 16 potential choices at that point.

Eliminate any number that has exclusively threes, exclusively nines, or one nine and one three.

Eliminate any number that is divisible by 11, except 11 itself, that wasn't already eliminated by the step above.

I get an upper bound of 11 prime numbers from that method.

A slightly different approach than 'Perhaps check it again'..

We need to only check divisibility by 2, 3, 5 and 7 for primes below 100. This rules out any prime starting with 2, 4, 5, 6 or 8 from our list (since the number after reversal will be divisible by 2 or 5). Divisibility by 3 is not affected by reversal. So we need to only check divisibility by 7.

That yields: 11, 13 (and 31), 17 (and 71), 37 (and 73), 79 (and 97).

Congratulations! The answer I had in mind was sort of a mix between these two answers, but both of yours are valid as well.

karthick was correct to note that we only had to check divisibility for primes under 10. Both of you were correct in ruling out the digits 2, 4, 5, 6, and 8. karthick's method of checking one side of each pair for divisibility by 3 was okay, but I preferred Perhap's ruling out of all numbers containing only 3s and 9s. I wish there was a cleaner way of culling out 77 because it's so obvious to rule out but I suppose either of your methods work (checking for divisibility by 7 or 11).

[Perhaps check it again]

I have the prime numbers less than 100 memorized, but I could give an upper bound instead.

 

Because we are reversing digits and necessarily want prime numbers, we have to

leave out numbers that begin or end with a digit of 0, 2, 4, 5, 6, or 8.

 

Then, for the potential two-digit prime number, there are four choices (1, 3, 7, 9) for the first

digit, and also for the second digit.

 

That is 16 potential choices at that point.

 

Eliminate any number that has exclusively threes, exclusively nines, or one nine and one three.

 

Eliminate any number that is divisible by 11, except 11 itself, that wasn't already eliminated by the step above.

 

I get an upper bound of 11 prime numbers from that method.

 

Edited October 31, 2014 by Perhaps check it again

[Perhaps check it again]

Note:  My upper bound was deliberately not meant to be thorough to the point of being the actual answer

to the question in the first line of the original post of this thread.

[karthickgururaj]

How many primes are the between 9 and 100 such that reversing the digits yields another prime?

This by itself is way too easy, so try to answer this using as little brute force as possible (or try to lower the upper bound as much as possible).

A slightly different approach than 'Perhaps check it again'..

 

We need to only check divisibility by 2, 3, 5 and 7 for primes below 100. This rules out any prime starting with 2, 4, 5, 6 or 8 from our list (since the number after reversal will be divisible by 2 or 5). Divisibility by 3 is not affected by reversal. So we need to only check divisibility by 7.

 

That yields: 11, 13 (and 31), 17 (and 71), 37 (and 73), 79 (and 97).