Palindromic Primes
Back to Problem Solutions forum
Very cool problem. Looks deceptively simple until you see the test data. :)
Thank you Sergei for a very fun addition to the exercises.
Yes, I suspected such a surprise, that’s why I immediately searched… and found the Miller-Rabin test.
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.
> 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 %)
There are 630 palindromic primes<10^6 and 5974 palindromic primes<10^8 (included 1-digit primes).
I found 11292 Emirp primes less 10 ** 9, but only one pair of them (37-73) has a index mirror property.
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)?
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.
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!
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... :)
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.
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. :)
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.
I'm not acquainted with this library (and with Python, silly me!) but it looks your guess is correct:
You see it looks like Miller-Rabin with some tuning and steroids.
My colleague tested emirp primes limited by 10 ** 11. And only one pair of them has the 'mirror index' property.
> 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