2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ By the way, the primes you are looking for (excluding palindromic primes) are called emirps and form OEIS sequence A006567. $\endgroup$ – A.P. Nov 9 '15 at 23:56
  • $\begingroup$ @ A. P.Very interesting. Thanks you very much for this information, dear friend. ("No hay nada nuevo bajo el Sol"...) $\endgroup$ – Piquito Nov 10 '15 at 11:48
  • $\begingroup$ By the way: according to the information given by A.P. this question IS NOT ELIGIBLE FOR BOUNTY, because already known. $\endgroup$ – Piquito Nov 10 '15 at 12:23
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ This is close any dreamed window towards the answer for larger n-digit primes. It does not interest at all to me. Thanks anyway. $\endgroup$ – Piquito Nov 9 '15 at 23:36
  • $\begingroup$ I don't think there are any known methods that scale well for large number of digits, though I hope to be proved wrong by some more knowledgeable member. $\endgroup$ – A.P. Nov 9 '15 at 23:54
  • $\begingroup$ It is not, please, looking about the prime $2^{57885161}-1$ with $17 425 170$ digits. $\endgroup$ – Piquito Nov 10 '15 at 12:02
  • $\begingroup$ You are way out of luck with that one, because that's the largest currently known prime number! Since it starts with $5$ and ends with $1$ its reverse is smaller. On the other hand, the second largest known prime number has $12978189$ digits (see here), therefore we don't know if $2^{57885161}−1$ is an emirp or not. $\endgroup$ – A.P. Nov 10 '15 at 14:49
  • $\begingroup$ This largest prime effectively ends in 1 (easy to prove). But how do you know that start with 5? Or do you seem more distracted than me and you are confusing the exponent with the prime?. Regards. $\endgroup$ – Piquito Nov 11 '15 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.