2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ look up IntegerDigits and Reverse $\endgroup$
    – george2079
    Apr 6, 2018 at 0:53
  • 1
    $\begingroup$ Is this a problem in Project Euler? $\endgroup$ Apr 6, 2018 at 1:23

3 Answers 3

4
$\begingroup$

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}
$\endgroup$
0
1
$\begingroup$

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}

Benchmark

$\endgroup$
2
  • $\begingroup$ I think here "prime-palindromic" does not have to be a palindrome number itself, according to the question description. $\endgroup$ Apr 11, 2018 at 6:42
  • $\begingroup$ Ups, sorry I totally got the question wrong :D Correcting it now... $\endgroup$ Apr 11, 2018 at 6:55
1
$\begingroup$
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}

$\endgroup$
2
  • $\begingroup$ I noticed that you have been editing some of your old answers to use prefix operators or the operator form of functions. I like to use postfix and right composition so that expressions can be read from left to right. The above answer written that way would be 5000 // PrimePi // Range // Prime // Select[IntegerReverse /* PrimeQ]. What are your thoughts on that vs. right to left? $\endgroup$ Nov 19, 2018 at 2:23
  • $\begingroup$ @RohitNamjoshi, i like prefix just because it saves some keystrokes. And IntegerReverse /* PrimeQ simply did not occur to me. $\endgroup$
    – kglr
    Nov 19, 2018 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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