Palindromic Primes

Back to Problem Solutions forum

Guy Gervais     2014-09-05 11:47:31
User avatar

Very cool problem. Looks deceptively simple until you see the test data. :)

Thank you Sergei for a very fun addition to the exercises.

nicolas_patrois     2014-09-05 12:04:54
User avatar

Yes, I suspected such a surprise, that’s why I immediately searched… and found the Miller-Rabin test.

Moff     2014-09-05 12:55:37
User avatar

There is an error in problem title.

Palindromic primes is primes that p=inverse(p), such as 101, 131, see Wiki.

But primes from problem are called Emirp, see Wiki.

Sorry, i swapped the terms when discribing to Rodion.

nicolas_patrois     2014-09-05 13:02:05
User avatar

The problem statement is clear: there is no palindrome but symmetric primes instead.

Searching for palindrome primes might be another problem but I suspect that there will be very few palindromic primes.

Moff     2014-09-05 13:02:53
User avatar

I found the interesting number 73 from TV-serial "The Big Bang Theory" (season 4, episode 10).

Rodion (admin)     2014-09-05 13:25:51
User avatar

> There is an error in problem title.

Wow, never heard of them :)

I'll try to edit problem title and statement to conform with this terminology :-o

> Looks deceptively

I spent about half an hour trying to understand why some random primes make the algorithm hang... At last I get that it is about primes starting with non-prime digit... Shame on me %)

nicolas_patrois     2014-09-05 19:07:29
User avatar

There are 630 palindromic primes<10^6 and 5974 palindromic primes<10^8 (included 1-digit primes).

Moff     2014-09-05 19:47:51
User avatar

I found 11292 Emirp primes less 10 ** 9, but only one pair of them (37-73) has a index mirror property.

Rodion (admin)     2014-09-05 19:49:15
User avatar

Funny that there should be 100 times more ordinary primes but only 10 times more palindromic ones.

By the way, while being prime is the core property of a number - being palindromic prime obviously depends on the numeral system. What do you think, without testing :) whether there are more palindromic primes in decimal, hexadecimal, binary or rather pentimal or heptimal system (for the same range, say up to 10^9)?

Guy Gervais     2014-09-05 20:31:46
User avatar

Intuitively, I would expect more in binary. It seems to me that the less different digits you use, the more likely you are to get palindromes.

Rodion (admin)     2014-09-06 05:01:12
User avatar

But intuitively binary is 3 times longer compared to corresponding decimal so the amount of digits which should correspond to the reverse is also 3 times greater!

Guy Gervais     2014-09-06 09:55:36
User avatar

Yes that's true. But my thinking was that if you had a "base 10^9" representation of numbers, you'd expect zero palindromes since each number from 2..max-prime-before-10^9 would have it's own representation. Single digit primes aren't considered palindromic (or emirps) since the palindrome of 3 is still 3.

So my intuition (my untested hypothesis would be a better term I guess) was that if "base 10^9" has zero palindromes and base 10 has a lot, then the lower the base, the more palindromes you would find. My intuition could also be completely wrong.

And now, thanks to you, I just have to go and check... :)

Guy Gervais     2014-09-06 10:45:29
User avatar

I just want to confirm something: I'm getting different counts for emirps and palindromes than what was previously posted:

If the limit is 10^6, I get 11,184 emirps and 113 palindromes.

If the limit is 10^9, I get 4,809,260 emirps and 5,953 palindromes.

For the emirps, I'm using wikipedia's definition that an emirp prime should give a different prime when read backwards. So 2, 5, 7, 11, 313 etc. are not emirps.

Guy Gervais     2014-09-06 11:10:32
User avatar

For representation in different bases (I'm testing base 2, 8, 10 and 16), I'm getting:

Limit is 10^6:                        Limit is 10^9:

Base Palindromes Emirps               Base Palindromes     Emirps
  2      187     19,036                 2     3,657     7,567,228
  8      208      8,028                 8     2,319     4,358,460
 10      113     11,184                10     5,953     4,809,260
 16      332     11,760                16     3,647     2,714,766

Whatever my intuition was, that's not what I expected. :)

Base 10 has the least palindromes below 10^6, but the most at 10^9... interesting. :)

Moriarty     2014-09-07 03:48:00
User avatar

I totally misread the question. When i read closest, I wrote a program that search both ways ( primes less than and greater than the given ones).

I used the sympy library for nextprime and prevprime function.

nicolas_patrois     2014-09-07 06:34:02
User avatar

You cheater! ;-)

Does this library use the Miller-Rabin test?

Rodion (admin)     2014-09-07 16:51:43
User avatar

I'm not acquainted with this library (and with Python, silly me!) but it looks your guess is correct:

source of primetest module

You see it looks like Miller-Rabin with some tuning and steroids.

Moff     2014-09-08 05:42:36
User avatar

My colleague tested emirp primes limited by 10 ** 11. And only one pair of them has the 'mirror index' property.

Rodion (admin)     2014-09-08 11:27:39
User avatar

> For representation in different bases (I'm testing base 2, 8, 10 and 16), I'm getting:

I investigated this bit further - as I proposed to check "heptimal" and "pentimal" sysmems.

It looks like the number of emirps is significantly larger if the base is prime. At the same time the "more composite" the base is, the better is the result.

For example, if I try first 100000 primes:

base    emirps
   2     11117
   3     10105
   4      8426
   5     10929
   6      3921
   7      9809
   8      4694
   9      6998
  10      5985
  11     11976
  12      2405
  13      7318
  14      5455
  15      7037
  16      7375
  17     11693
  18      3546
Please login and solve 5 problems to be able to post at forum