According toWikipedia, "an emirp is a prime number that results in a different prime when its decimal digits are reversed". For example, the prime 13 is an emirp since 31 is also prime.
I have a list of primes. I know they are primes. I want to efficiently determine if they are emirps.
Here is my current algorithm:
- Cut all candidate terms in the list beginning with 2,4,5,6,8
- Reverse remaining terms, and use Miller-Rabin composite test
I don't believe this is optimal.
What other mathematical shortcuts can I use to eliminate candidates without running the full primality test? I'm particularly interested in digit patterns or number theory properties that guarantee a reversed number will be composite, similar to the first step of my algorithm.
Is there any literature on the rapid identification of emirps? I wasn't able to find any.
Edits: Simplified question, clarified somewhat.
- $\begingroup$Well,.... the exact same procedures one would use to determine if a string of digits were prime would work just in the other order. No number ending in an even number can be prime so no numberbegining with an even number can be Emirp. And not number were the digits add to a multiple of $3$ can be prime so the same about Emirp. Every rule for primes relating to digits can be reversed to emirps and vice versa " but I suspect there are more elegant mathematical shortcuts I'm missing" why would you think that? They should be utterly equivalent.$\endgroup$fleablood– fleablood2025-06-18 05:20:31 +00:00CommentedJun 18 at 5:20
- $\begingroup$I was hoping that there would be some sort of trick that applies specifically to Emirps that one could exploit. If one already knows that the original number is prime, is there any information that can be used with that to determine, in a faster way, whether or not the reverse of that number is prime? In other words, does the knowledge that a number is prime help you determine if it is also an Emirp?$\endgroup$Peter El Ghazal– Peter El Ghazal2025-06-18 05:23:47 +00:00CommentedJun 18 at 5:23
- $\begingroup$Okay. I didn't get that the number had to be prime in the first place. Hmm.... I really doubt there is anything one can do. After all digits are pretty arbitrary based on base.$\endgroup$fleablood– fleablood2025-06-18 05:28:14 +00:00CommentedJun 18 at 5:28
- $\begingroup$Your funny name "Emirp" should be something like "EmirpTen" in order to specify which base ($10$) you are considering ($10$ is a peculiar base). Please note that the EmirpTwo set for example deserves a similar investigation...$\endgroup$Jean Marie– Jean Marie2025-07-18 10:20:01 +00:00CommentedJul 18 at 10:20
- $\begingroup$@JeanMarie "Emirp" is not dreamt up by the user, it is the official name, and base 10 is specifiedmathworld.wolfram.com/Emirp.html ("An emirp ("prime" spelled backwards) is a prime whose (base 10) reversal is also prime, but which is not a palindromic prime.")$\endgroup$DrM– DrM2025-07-18 10:46:07 +00:00CommentedJul 18 at 10:46
2 Answers2
Most commonprimality tests applied to large numbers are unrelated to the base the number is written in, so they will not involve any property of the digits of the number itself.
The standard tests for divisibility by 3 and 11 using a number's digitsdo carry through to the reverse of a number. In the case of divisibility by 3, you're just adding the digits together, and in the case of divisibility by 11 you alternately add and subtract the digits, so it's easy to see that the test gives the same results when the digits are reversed. For digit-based tests of other factors, though, you typically have to group digits together and that breaks down as soon as you reverse the number.
Primality testing normally starts out with some degree of testing for divisibility by small primes. There's a fast way to test for divisibility without using costly modulus or division operations, but instead uses some pre-calculated constants. There's a description and a short list of constants herehttps://lomont.org/posts/2017/divisibility-testing/.
Since you require both the integer and its reverse to be prime, you can test both at the same time for divisibility by small primes to sieve out many composites so you only have to perform a more expensive test like Miller Rabin on a small subset of the range you're exploring.
If you want it to be fast, I strongly recommend using some low level language like c rather than Python. If you get really serious, the sieving part can be done efficiently on a GPU in a similar way to how I found the results to this question hereCan I prepend a digit to some number finitely many times and always get primes, for arbitrarily long finite lengths?.
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.