## Emirps

### November 2, 2010

An emirp is a prime number that is also prime when its digits are reversed, and that is not also a palindrome. For instance, 13 is an emirp because its reversal, 31, is also prime; 23 is not an emirp, even though it is prime, because its reversal, 32, is not prime; and 101 is not an emirp, even though it is prime, because it is a palindrome.

Your task is to enumerate the emirps below a million; you should strive for maximum speed. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 16 Responses to “Emirps”

1. [...] Praxis – Emirps By Remco Niemeijer In today’s Programming Praxis, our task is to enumerate all the non-palindrome prime numbers that are still [...]

2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/02/programming-praxis-emirps/ for a version with comments):

```import Data.Numbers.Primes

emirps :: [Integer]
emirps = [p | p <- primes, let rev = reverse (show p)
, isPrime (read rev), show p /= rev]

main :: IO ()
main = print \$ takeWhile (< 1000000) emirps
```
3. Here is my Haskell solution: http://www.gleocadie.net/?p=178&lang=en

```import Data.List

isPrime l =
isPrimeHelper l primes

isPrimeHelper a (p:ps)
| p*p > a = True
| a `mod` p == 0 = False
| otherwise = isPrimeHelper a ps

primes = 2 : filter isPrime [3,5..]

permirps = drop 4 (takeWhile (<1000000) primes)

isEmirps x =
let sx = show x in
let rev = reverse sx in
sx /= rev &&  isPrimeHelper (read rev) primes

emirps = filter isEmirps permirps

main = print \$ emirps
```

4. fengshaun said

I’m loving this website! Thanks a lot for the problems.

```import Data.Numbers.Primes

emirps :: [Integer]
emirps = filter (\a -> isEmirp a) . filter (\a -> not . isPalindrome \$ a) . takeWhile (< 1000000) \$ primes
where
isPalindrome :: Integer -> Bool
isPalindrome x = (reverse . show \$ x) == (show x)

isEmirp :: Integer -> Bool
isEmirp x = isPrime . read . reverse . show \$ x

main :: IO ()
main = print . show \$ emirps
```
5. fengshaun said

I’m loving this website, thanks a lot!

```import Data.Numbers.Primes

emirps :: [Integer]
emirps = filter (\a -> isEmirp a) . filter (\a -> not . isPalindrome \$ a) . takeWhile (< 1000000) \$ primes
where
isPalindrome :: Integer -> Bool
isPalindrome x = (reverse . show \$ x) == (show x)

isEmirp :: Integer -> Bool
isEmirp x = isPrime . read . reverse . show \$ x

main :: IO ()
main = print . show \$ emirps
```
6. Joe Eisenberg said

Love the site.

```from math import sqrt

def prime(number):
if number == 2:
return True
f = round(sqrt(number))
for n in range(3,int(f)+1,2):
if number % n == 0:
return False
return True

for n in range(1000001,11,-2):
if prime(n):
if prime(int(str(n)[::-1])):
print str(n) + ":" + str(n)[::-1]
```
7. Joe Eisenberg said

Sorry, line 14 should read

if prime(int(str(n)[::-1])) and str(n) != str(n)[::-1]:

8. Graham said

@Joe: your prime() function isn’t quite correct. For instance, prime(10) returns True.

9. Graham said

Wrote it in python (though for speed, a different language may be better). In the interest of speed, I wrote a function called reverse(n) that writes n backwards using only numerical operations (avoiding strings). Interestingly, trying to memoize my is_prime() function made everything slower (perhaps due to memory usage?). Running ./emirps.py 1000000 took just under 15 seconds on my aging laptop. For more speed I used pypy (Python with a just in time compiler); it finished in just under 3 seconds.

```#!/usr/bin/env python2.6

import math

def reverse(n):
"""
Given integer n, returns n written backwards.
Note: uses only numerical operations (not string ones) for speed.
"""
d, r = 0, 0
while n > 0:
l = int(math.log10(n))
r += (10 ** d) * (n // (10 ** (l)))
d += 1
n %= (10**l)
return r

def is_prime(n):
"""
Simple check for primality, testing n mod k for odd k up to 1 + sqrt(n).
"""
if n == 2:
return True
elif n % 2 == 0:
return False
else:
for k in xrange(3, 1 + int(math.sqrt(n)), 2):
if n % k == 0:
return False
return True

def main(n):
"""
Prints out all emirps less than n.
"""
for p in xrange(2, n):
r = reverse(p)
if (is_prime(p)) and (r != p) and (is_prime(r)):
print p

if __name__ == '__main__':
import sys
main(int(sys.argv[1]))
```
10. Graham said

Changing line 36 in main(n) from

```for p in xrange(2, n):
```

to

```for p in xrange(13, n, 2):
```

yields a decent speed up; normal execution finishes in just under 11 seconds, while pypy finishes it in under 2.

11. turuthok said

Probably if you avoid using math.log10(n), you’ll end up with a faster execution.

12. My C Implementation
This one was easy one. ;)

13. My C Implementation
This one was easy one. ;)

14. David said

We can build on the sieve of Erastosthenes exercise to create a list of primes < 1,000,000. Since the output array of the sieve is sorted, we can use binary search on the table for O(log n) search of the sieve, when checking for whether each reversal is prime. The Factor code for sieve is already posted on this blog and won't be reproduced here.

USING: kernel sequences vectors math math.parser locals
binary-search sieve ;
IN: emirp

: emirp? ( n vec — ? )
swap
number>string dup reverse 2dup =
[ 3drop f ]
[ nip string>number swap sorted-member? ] if ;

:: emirp-filter ( primes — semirp )
V{ } clone
primes
[ dup primes emirp?
[ suffix ]
[ drop ] if
] each ;

: Semirp ( n — vec )
primes emirp-filter ;

Factor session:

( scratchpad ) 100000 Semirp

— Data stack:
V{ 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199…
( scratchpad ) length .
1646

15. David said

Sorry, somehow the code block didn’t work on last post, probably got a tag wrong somewhere…

We can build on the sieve of Erastosthenes exercise to create a list of primes < 1,000,000. Since the output array of the sieve is sorted, we can use binary search on the table for O(log n) search of the sieve, when checking for whether each reversal is prime. The Factor code for sieve is already posted on this blog and won't be reproduced here.

USING: kernel sequences vectors math math.parser locals
binary-search sieve ;
IN: emirp

: emirp? ( n vec — ? )
swap
number>string dup reverse 2dup =
[ 3drop f ]
[ nip string>number swap sorted-member? ] if ;

:: emirp-filter ( primes — semirp )
V{ } clone
primes
[ dup primes emirp?
[ suffix ]
[ drop ] if
] each ;

: Semirp ( n — vec )
primes emirp-filter ;

Factor session:

( scratchpad ) 100000 Semirp

— Data stack:
V{ 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199…
( scratchpad ) length .
1646