Primes whose mirror is prime

Question

I am interested in finding a method to determine all four-digit primes (notation $ p = xyzw $) such that (its mirror) $ q = wzyx$ is also a prime in other words, to solve the system with digits $x,y,z,w; \space xw\ne 0$. $$\begin{cases} 1000x+100y+10z+w = prime\\1000w+100z+10y+x= prime\end{cases}$$ Some examples of solutions are $xyzw=1009, 1031, 1033, 1061, 1091, 1103, 1151, 9041, 9967$. For two-digit primes there are the four solutions: $$13,17,37\space \text{and}\space79$$ and for three digit-primes (discarded the fifteen trivial solutions $101,131,151, 181, 191, 313, 353, 373, 383, 727, 757,787, 797, 919$ and $929$) there are the fourteen ones: $$107,113,149,157,167,179,199,337,347,359,389,709, 739\space \text{and}\space769$$
The "method" used to determine this is easy to guess (brute force some people say). I wonder about a method without quotation marks. We note first that, unlike the case of three-digit primes, in the case we try of four- digit primes there is no trivial solution, because all number of the form $ abba $ is divisible by $11$. I have these restrictions so far: $$\begin{cases}1)\space1009\le1000x+100y+10z+w\le9967\\2)\space{\{x,w}\}\subset{\{1,3,7,9}\} \\3)\space x+y+z+w=3m\pm1\space\text{(i.e. not multiple of 3)}\\4)\space (x+z)-(y+w)\ne 11k \space\text{(i.e. not multiple of 11)}\\5) \text{ other criteria for divisibility}\end{cases}$$ Constraint $1)$ comes from the "method" used for two-digit and three-digit primes (i.e. $1009$ is the smallest solution and $9067$ is the greatest one).

Constraint $2)$ allows us to transform the system $$\begin{cases} 1000x+100y+10z+w = prime\\1000w+100z+10y+x= prime\end{cases}$$ of four unknowns $x,y,z,w$ in sixteen systems $$\begin{cases} 1000a+100y+10z+b = prime\\1000b+100z+10y+a= prime\end{cases}$$ of two unknowns $y,z$ with $a,b= 1,3,7,9$

Apply divisibility criteria(constraint $3)$, $4)$ and $5)$ could also perhaps help.

What's needed to have a solution method without quotation marks, I mean without comparing all of the four-digit primes in a table? Is it possible?

Answer 1

Actually, enumeration — or brute force, as you call it — is a perfectly viable proof technique; sometimes the only one available.

While I don't know if it is the case here, this is the list of all solutions to your problem (I didn't bother pruning the reversed pairs) $$ 1009, 1021, 1031, 1033, 1061, 1069, 1091, 1097, 1103, 1109, 1151, 1153, 1181, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1279, 1283, 1301, 1321, 1381, 1399, 1409, 1429, 1439, 1453, 1471, 1487, 1499, 1511, 1523, 1559, 1583, 1597, 1601, 1619, 1657, 1669, 1723, 1733, 1741, 1753, 1789, 1811, 1831, 1847, 1867, 1879, 1901, 1913, 1933, 1949, 1979, 3011, 3019, 3023, 3049, 3067, 3083, 3089, 3109, 3121, 3163, 3169, 3191, 3203, 3221, 3251, 3257, 3271, 3299, 3301, 3319, 3343, 3347, 3359, 3371, 3373, 3389, 3391, 3407, 3433, 3463, 3467, 3469, 3511, 3527, 3541, 3571, 3583, 3613, 3643, 3697, 3719, 3733, 3767, 3803, 3821, 3851, 3853, 3889, 3911, 3917, 3929, 7027, 7043, 7057, 7121, 7177, 7187, 7193, 7207, 7219, 7229, 7253, 7297, 7321, 7349, 7433, 7457, 7459, 7481, 7507, 7523, 7529, 7547, 7561, 7577, 7589, 7603, 7643, 7649, 7673, 7681, 7687, 7699, 7717, 7757, 7817, 7841, 7867, 7879, 7901, 7927, 7949, 7951, 7963, 9001, 9011, 9013, 9029, 9041, 9103, 9127, 9133, 9161, 9173, 9209, 9221, 9227, 9241, 9257, 9293, 9341, 9349, 9403, 9421, 9437, 9439, 9467, 9479, 9491, 9497, 9521, 9533, 9547, 9551, 9601, 9613, 9643, 9661, 9679, 9721, 9749, 9769, 9781, 9787, 9791, 9803, 9833, 9857, 9871, 9883, 9923, 9931, 9941, 9967 $$ which I found with this simple Sage script

def reverse(n):
    return int(str(n)[::-1])

def reversed_is_prime(n):
    return is_prime(reverse(n))

def rev_primes(digits):
    return filter(reversed_is_prime, prime_range(10^(digits-1),10^digits))

print(rev_primes(4))

and here's a little benchmark on my (oldish) Intel i5-2500K

sage: for i in range(2,9):
....:     print("Time to compute reverse primes with {0} digits:".format(i))
....:     %timeit rev_primes(i)
....:     print
....:     
Time to compute reverse primes with 2 digits:
10000 loops, best of 3: 89.2 µs per loop

Time to compute reverse primes with 3 digits:
1000 loops, best of 3: 697 µs per loop

Time to compute reverse primes with 4 digits:
100 loops, best of 3: 4.54 ms per loop

Time to compute reverse primes with 5 digits:
10 loops, best of 3: 36.1 ms per loop

Time to compute reverse primes with 6 digits:
1 loops, best of 3: 300 ms per loop

Time to compute reverse primes with 7 digits:
1 loops, best of 3: 2.66 s per loop

Time to compute reverse primes with 8 digits:
1 loops, best of 3: 24.1 s per loop