Lists of Numbers

Question

An integer is prime-palindromic if both orientations are prime (i.e. 941 <--> 149) Write a function to test if an integer, n, is prime-palindromic. Which numbers in 1

I took the approach;

With[{list = Range[5000]}, Pick[list, PrimeQ[PalindromeQ[list]]]]

This doesn't seem to work, and even if it did, it wouldn't typically satisfy for the reverse values being equal to a prime?

Answer 1

IntegerReverse could be helpful.

filter = Select[And @@ PrimeQ @ {#, IntegerReverse[#]} &];
filter[Range[5000]]

gives

{2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, \
 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, \
 373, 383, 389, 701, 709, 727, 733, 739, 743, 751, 757, 761, 769, 787, \
 797, 907, 919, 929, 937, 941, 953, 967, 971, 983, 991, 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}

Answer 2

UPDATA: I initially misunderstood the question, but the key points there are still valid: Instead of checking numbers to be prime, just generate the list of first, say, 1000 primes, take their reverses and take the intersection. Namely,

Timing[Intersection[Prime@Range[10^#],IntegerReverse@Prime@Range[10^#]]&[3]] 

finds all prime-palindromic numbers within first $10^4$ prime numbers within 0.005 seconds:

{0.004286, {2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389, 701, 709, 727, 733, 739, 743, 751, 757, 761, 769, 787, 797, 907, 919, 929, 937, 941, 953, 967, 971, 983, 991, 1021, 1031, 1033, 1061, 1091, 1097, 1103, 1151, 1153, 1181, 1193, 1201, 1213, 1217, 1223, 1231, 1237, 1283, 1301, 1321, 1381, 1453, 1471, 1487, 1511, 1523, 1583, 1601, 1657, 1723, 1733, 1741, 1753, 1811, 1831, 1847, 1867, 1901, 1913, 1933, 3011, 3023, 3067, 3083, 3121, 3163, 3191, 3203, 3221, 3251, 3257, 3271, 3301, 3343, 3347, 3371, 3373, 3391, 3407, 3433, 3463, 3467, 3511, 3527, 3541, 3571, 3583, 3613, 3643, 3733, 3767, 3803, 3821, 3851, 3853, 3911, 3917, 7027, 7043, 7057, 7121, 7177, 7187, 7193, 7207, 7253, 7321, 7433, 7457, 7481, 7507, 7523, 7547, 7561, 7577, 7603, 7643, 7673, 7681, 7687, 7717, 7757, 7817, 7841, 7867, 7901}}

Note that the presence of intersection means we are treating generated primes and their reverses symmetrically, hence the list above does not include any prime whose reverse is not within the first 1000 primes. For example, 3929 is not in the list as its reverse 9293 is above 1000th prime 7919. Therefore, the safest method is always generate more primes than necessary and cut off irrelevant ones: This is not a problem as the code is sufficiently fast:

generator = Intersection[Prime@Range[10^#], IntegerReverse@Prime@Range[10^#]] &;
Pick[generator@4, UnitStep[5000 - generator@4], 1] // Timing 

gives the result

{0.102224, {2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389, 701, 709, 727, 733, 739, 743, 751, 757, 761, 769, 787, 797, 907, 919, 929, 937, 941, 953, 967, 971, 983, 991, 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}}

Note the vectorized usage of UnitStep with Pick. Even though these are not relevant at this order, they may be crucial for larger lists.

---

OLD ANSWER:

There is already the command PalindromeQ, so simplest command would be

Select[Prime@Range[100000], PalindromeQ] // Timing

which gives the Palindromic numbers among the first 100,000 prime numbers under 0.6 seconds:

{0.579166, {2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821}}

For larger lists, Select may be not the optimum command; its vectorized version Pick would probably be faster. For that, we also need a listable version of PalindromeQ, which we can define as

palindromeQ[a_] := PalindromeQ[a];
SetAttributes[palindromeQ, Listable];

Following command generates the same result

Pick[#, palindromeQ[#]] &[Prime @ Range[100000]] // Timing

which is at comparable time with Select. At this order Select is faster, but I think Pick would be the better choice for larger numbers.

Note that one key point above is not to check all numbers from scratch, but generate only prime numbers and test if they are palindromic.

---

I did a small benchmark: Contrary to what I claim, Select seems to be faster than Pick, though I still believe it would change if we consider even larger sets (maybe my palindromeQ was not the right way to utilize Pick fully?). Either way, both methods are linearly complex, that is the time they take to calculate increases linearly with the number of primes we consider.

Table[Timing[Select[Prime@Range[10^a], PalindromeQ]][[1]], {a, 1, 7}]

{0.000086, 0.000467, 0.004861, 0.054756, 0.584495, 7.1616, 76.0888}

Table[Timing[Pick[#, palindromeQ[#]] &[(Prime@Range[10^a])]][[1]], {a, 
1, 7}]

{0.00019, 0.001001, 0.00795, 0.056908, 0.725514, 7.63905, 79.0614}

Answer 3

Select[PrimeQ @* IntegerReverse] @ Prime @ Range @ PrimePi @ 5000

{2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389, 701, 709, 727, 733, 739, 743, 751, 757, 761, 769, 787, 797, 907, 919, 929, 937, 941, 953, 967, 971, 983, 991, 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}