# Most palindromic prime numbers

A prime number is the most palindromic prime if it has more nontrivial palindromic representations across number bases than all primes below it.

Nontrivial representation means we are not counting one digit representations as palindromes (since number $p$ is one-digit-palindromic in all number bases $b\gt p$), and we are also not counting the "$11$" representation since every $p$ can be written like that in the base $b=p-1$.
In other words, we are considering the number bases $b\le p-2$ only.

I've found that it is sufficient to check number bases $b\le \lfloor\sqrt p\rfloor+1$
(This excludes $2$ digit representations as they are composite and divisible by $a$ for digits $a\ge2$)

I've computed the first $21$ terms so far, below:
(checked / iterated over the first $10^6$ prime numbers so far)

Read Columns: $1 -$ the prime number, $2 -$number of palindromic representations (number bases), $3 -$ index of the prime number, $4 -$ number bases in which the prime number is palindromic

2 0 1. []
5 1 3. 
17 2 7. [2, 4]
191 3 43. [6, 9, 10]
257 4 55. [2, 4, 7, 16]
1009 5 169. [11, 15, 19, 24, 28]
4561 6 618. [4, 31, 47, 48, 57, 60]
4591 7 621. [19, 20, 24, 33, 37, 51, 54]
21601 8 2426. [12, 29, 33, 69, 108, 120, 135, 144]
54121 10 5510. [46, 47, 50, 61, 70, 76, 87, 165, 205, 220]
86677 11 8424. [2, 48, 58, 64, 66, 70, 94, 107, 113, 151, 233]
176401 12 16031. [59, 69, 73, 136, 300, 315, 336, 350, 360, 392, 400, 420]
291721 14 25365. [122, 146, 148, 172, 205, 233, 311, 390, 408, 429, 440, 442, 510, 520]
950041 15 74912. [138, 152, 192, 219, 239, 696, 728, 754, 780, 812, 819, 840, 870, 910, 936]
1259701 16 97165. [126, 147, 184, 185, 199, 279, 299, 423, 850, 884, 950, 969, 975, 988, 1020, 1105]
1670761 18 126103. [10, 121, 161, 348, 591, 918, 936, 945, 952, 1020, 1071, 1080, 1092, 1105, 1170, 1190, 1224, 1260]
3880801 20 275324. [40, 369, 388, 472, 1400, 1440, 1470, 1540, 1568, 1575, 1584, 1617, 1650, 1680, 1760, 1764, 1800, 1848, 1925, 1960]
5654881 21 390695. [249, 387, 977, 1683, 1760, 1785, 1836, 1848, 1870, 1890, 1904, 1980, 2016, 2040, 2079, 2142, 2160, 2244, 2295, 2310, 2376]
13759201 22 895446. [292, 528, 1253, 2646, 2700, 2730, 2800, 2808, 2912, 2925, 2940, 3024, 3120, 3150, 3185, 3276, 3360, 3510, 3528, 3600, 3640, 3675]
14414401 24 935289. [262, 2730, 2772, 2800, 2860, 2880, 2912, 2925, 3003, 3080, 3120, 3150, 3168, 3276, 3300, 3360, 3432, 3465, 3520, 3575, 3600, 3640, 3696, 3744]
15135121 26 978870. [292, 473, 533, 611, 1565, 2772, 2808, 2860, 2940, 2970, 3003, 3024, 3080, 3120, 3185, 3234, 3276, 3432, 3465, 3510, 3528, 3640, 3696, 3780, 3822, 3861]


This sequence is not in the OEIS.

I've noticed that all terms so far except the $4$-th $(191)$ and $8$-th one $(4591)$, are a hypotenuse of a primitive pythagorean triple and can be written as a sum of two squares ($p=4k+1$).
These two 'rouge' terms cannot be written as a sum of three squares ($p=8k+7$).

You can also notice that some primes on the list are better than previous by two bases, rather than by just one more as most so far.

Have primes generated by this property been observed before? Are there any other properties they might share?

How can they be generated/computed faster than checking every prime for being palindromic in every number base up to $\lfloor\sqrt p\rfloor+1$, and adding it to the list if it beats the current record?

To speed up the search; Perhaps a lower bound on gaps between two consecutive terms can be found or properties that exclude some sets of number bases can be stated?

• Most of the research on palindromic numbers has focused on base 10 palindromes, and a decent amount on binary palindromes. Other bases have for the most part been ignored. – Mr. Brooks Dec 9 '17 at 22:24
• Suppose $b$ is a two-digit palindrome in some base $b$, then $p=ab+a=a(b+1)$ for some $a$. Since $p$ is prime, this gives $a=1$, so $p=11_b$, but that's forbidden. So $p$ is at least a three-digit palindrome, giving $101_b=b^2+1\ge p$, so that's why you found $b\le\lfloor\sqrt{p}\rfloor+1$. – Mastrem Dec 9 '17 at 22:38
• @Mastrem That's what I meant to say when I wrote that we are excluding $2$ digit examples. – Vepir Dec 10 '17 at 16:13