# Find the Emirps!

An emirp is a non-palindromic prime which, when reversed, is also prime.

The list of base 10 emirps can be found on OEIS. The first six are:

13, 17, 31, 37, 71, 73


However, due to the reversal rule, emirps are different in each base. For example, the first six binary emirps are:

Bin  | 1011, 1101, 10111, 11101, 101001, 100101
Dec  | (11 , 13  , 23   , 29   , 37    , 41   )


Hex |  17, 1F, 35, 3B, 3D, 53
Dec | (23, 31, 53, 59, 61, 83)


Fun Fact: there are no emirps in unary as every number is a palindrome.

# The Challenge

Your task is to create a function (or full program) which takes two parameters, $$\ n \$$ and $$\ b \$$, and generates a list of the first $$\ n \$$ emirps in base $$\ b \$$.

Rules/Details:

• $$\ n \$$ and $$\ b \$$ are both positive integers larger than $$\ 0 \$$.
• You can assume $$\ 2 ≤ b ≤ 16 \$$: that is to say, the base will be between binary and hexidecimal.
• You should be able to compute for values of $$\ n \$$ up to $$\ ~100 \$$.
• The generated list can be in base $$\ b \$$, or your language's standard integer base, as long as you specify this in your answer.
• Builtin emirp checks are not permitted (builtin primality tests are fine)
• You cannot hard-code the emirps, or read from any external files.
• Standard loopholes are banned, as always.
• This is , so the shortest answer (in bytes) wins.

# Test Cases

For each test case, I've included the list in base b and its base 10 equivalents.

B = 2, N = 10

BIN: [1011, 1101, 10111, 11101, 100101, 101001, 101011, 101111, 110101, 111101]
DEC: [11, 13, 23, 29, 37, 41, 43, 47, 53, 61]

B = 3, N = 5

BASE3: [12, 21, 102, 201, 1011]
DEC:   [5, 7, 11, 19, 31]

B = 12, N = 7

BASE12: [15, 51, 57, 5B, 75, B5, 107]
DEC: [17, 61, 67, 71, 89, 137, 151]

B = 16, N = 4

HEX: [17, 1F, 35, 3B]
DEC: [23, 31, 53, 59]


You can test your program further against my (ungolfed) Python example on repl.it

# Jelly, 16 bytes

bµU,ḅ⁹QÆPḄ=3
⁸ç#


TryItOnline!

### How?

bµU,ḅ⁹QÆPḄ=3 - Link 1, in-sequence test: n, b
b            - convert n to base b - a list
U          - reverse the list
,         - pair with the list
⁹       - link's right argument, b
ḅ        - convert each of the two lists from base b
Q      - get unique values (if palindromic a list of only one item)
ÆP    - test if prime(s) - 1 if prime, 0 if not
Ḅ   - convert to binary
=3 - equal to 3? (i.e. [reverse is prime, forward is prime]=[1,1])

⁸ç# - Main link: b, N
# - count up from b *see note, and find the first N matches (n=b, n=b+1, ...) for:
ç  - last link (1) as a dyad with left argument n and right argument
⁸   - left argument, b


* Note b in base b is [1,0], which when reversed is [0,1] which is 1, which is not prime; anything less than b is one digit in base b and hence palindromic.

• Congrats on winning! – FlipTack Nov 16 '16 at 17:29

# 05AB1E, 17 bytes

Uses CP-1252 encoding.

Input order is n, b
Output is in base-10.

µN²BÂD²öpŠÊNpPD–½


Try it online!

Explanation

                    # implicit input a,b
µ                   # loop until counter is a
N²B                # convert current iteration number to base b
ÂD              # create 2 reversed copies
²ö            # convert one reversed copy to base 10
p           # check for primality
ŠÊ         # compare the normal and reversed number in base b for inequality
Np       # check current iteration number for primality
P      # product of all
D     # duplicate
–    # if 1, print current iteration number
½   # if 1, increase counter


## Mathematica, 70 bytes

Cases[Prime@Range@437,p_/;(r=p~IntegerReverse~#2)!=p&&PrimeQ@r]~Take~#&


Works for 0 <= n <= 100 and 2 <= b <= 16. From the list Prime@Range@437 of the first 437 primes, find the Cases pwhere the IntegerReverse r of p in base #2 is not equal to p and is also prime, then take the first # such p.

Here's a 95 byte solution that works for arbitrary n>=0 and b>=2:

(For[i=1;a={},Length@a<#,If[(r=IntegerReverse[p=Prime@i,#2])!=p&&PrimeQ@r,a~AppendTo~p],i++];a)&

• +1 IntegerReverse. Of course! Nice. – DavidC Jan 3 '17 at 16:06
• 79 bytes for the arbitrary-n-b solution; 77 bytes if Reaping is allowed in the footer: For[i=j=0,j<#,If[(r=IntegerReverse[p=Prime@++i,#2])!=p&&PrimeQ@r,j++;Sow@p]]& – Roman Jun 23 at 12:49

# Perl, 262 bytes

($b,$n)=@ARGV;$,=',';sub c{my$z;for($_=pop;$_;$z=(0..9,a..z)[$_%$b].$z,$_=($_-$_%$b)/$b){};$z}sub d{my$z;for(;c(++$z)ne@_;){}$z}for($p=2;@a<$n;$p++){$r=qr/^1?$|^(11+?)\1+$/;(c($p)eq reverse c$p)||((1x$p)=~$r)||(1x d($x=reverse c($p)))=~$r?1:push@a,c($p);}say@a  Readable: ($b,$n)=@ARGV;$,=',';
sub c{
my$z; for($_=pop;$_;$z=(0..9,a..z)[$_%$b].$z,$_=($_-$_%$b)/$b){};
$z } sub d{ my$z;
for(;c(++$z)ne@_;){}$z
}
for($p=2;@a<$n;$p++){$r=qr/^1?$|^(11+?)\1+$/;
(c($p)eq reverse c$p)||((1x$p)=~$r)||(1x d($x=reverse c($p)))=~$r?1:push@a,c($p)
}
say@a


c converts a given number into base $b, and d converts a given number from base $b back into decimal by finding the first number which returns said base-$b number when passed to c. The for loop then checks if it's a palindrome and if both of the numbers are prime using the composite regex. # Mathematica 112 bytes Cases[Table[Prime@n~IntegerDigits~#2,{n,500}],x_/;x!=(z=Reverse@x)&&PrimeQ[z~(f=FromDigits)~#2]:>x~f~#2]~Take~#&  Example Find the first 10 Emips in hex; return them in decimal. Cases[Table[Prime@n~IntegerDigits~#2, {n, 500}], x_ /; x != (z = Reverse@x) && PrimeQ[z~(f = FromDigits)~#2] :> x~f~#2]~Take~# &[10, 16] {23, 31, 53, 59, 61, 83, 89, 113, 149, 179}  Ungolfed Take[Cases[ (* take #1 cases; #1 is the first input argument *) Table[IntegerDigits[Prime[n], #2], {n, 500}], (* from a list of the first 500 primes, each displayed as a list of digits in base #2 [second argument] *) x_ /; (* x, a list of digits, such that *) x != (z = Reverse[x]) && PrimeQ[FromDigits[z, #2]] (* the reverse of the digits is not the same as the list of digits; and the reverse list, when composed, also constitutes a prime *) :> FromDigits[x, #2]], (* and return the prime *) #1] & (* [this is where #1 goes, stating how many cases to Take] *)  # Perl 6, 91 bytes ->\n,\b{(grep {.is-prime&&{$_ ne.flip &&.parse-base(b).is-prime}(.base(b).flip)},1..*)[^n]}


Returns the list of emirps in base 10.

# Python 3, 232214191 188 bytes

p=lambda n:all(n%i for i in range(2,n))
def f(b,n):
s=lambda n:(''if n<b else s(n//b))+f'{n%b:X}';l=[];i=3
while n:i+=1;c=s(i);d=c[::-1];a=(c!=d)*p(i)*p(int(d,b));l+=[c]*a;n-=a
return l


Try it online!

• 200 bytes – Herman L Jun 25 at 22:11
• Nice catch! Brought that down to 191 bytes – movatica Jun 25 at 22:18
• Nice one, @JoKing! – movatica Jun 26 at 17:47

# C, 293286 261 bytes

Improved by @ceilingcat, 261 bytes:

v,t,i,j,c,g,s,r,b;main(n,a)int**a;{for(b=n=atoi(a);g^atoi(a);t|v|!wcscmp(s,r)||printf("%u ",n,++g)){i=j=0;for(c=++n;s[i]=c;c/=b)s[i++]=c%b+1;for(;r[j]=i;)r[j++]=s[--i];p(n);for(t=v;r[i];)c+=~-r[i]*pow(b,i++);p(c);}}p(n){for(j=1,v=0;++j<n;n%j||v++);}


Try it online!

(This person is like constantly following me around PPCG and improving my stuff in the comments, and as soon as I reply to thank him he just deletes the comment and vanishes lol. Welp, thanks again!)

Improved by @movatica, 286 bytes:

u,v,t,i,j,c,n,g;main(int x,char**a){char s,r,b=n=atoi(a);x=atoi(a);for(;g^x;){i=j=0;for(c=++n;c;c/=b)s[i++]=c%b+1;s[i]=c=0;for(;i;r[j++]=s[--i]);r[j]=0;p(n);t=v;for(;r[i];)c+=(r[i]-1)*pow(b,i++);p(c);t|v|!strcmp(s,r)?:printf("%u ",n,++g);}}p(n){for(u=1,v=0;++u<n;n%u?:v++);}


Try it online!

u,v,t,i,j,c,n,g;main(int x,char**a){char s,r,b=n=atoi(a);x=atoi(a);for(++n;g^x;++n){i=j=0;for(c=n;c;c/=b)s[i++]=c%b+1;s[i]=c=0;for(;i;r[j++]=s[--i]);r[j]=0;p(n);t=v;for(--i;r[++i];)c+=(r[i]-1)*pow(b,i);p(c);t|v|!strcmp(s,r)?:printf("%u ",n,++g);}}p(n){for(u=1,v=0;++u<n;n%u?:v++);}


Compile with gcc emirp.c -o emirp -lm and run with ./emirp <b> <n>. Prints space-separated emirps in base-10.

• @FlipTack You're right. I'll have to fix it tomorrow. – OverclockedSanic Jun 23 at 20:32
• @FlipTack Fixed and tested to make sure it passes your tests. Is this good? – OverclockedSanic Jun 24 at 13:02
• Sure is! And welcome to code golf. – FlipTack Jun 24 at 17:52
• Nice work! I moved some increment operators to get you down to 286 – movatica Jun 25 at 21:15
• @movatica Awesome! I added your improvements to my answer. Thanks! – OverclockedSanic Jun 26 at 10:43

## JavaScript (ES6), 149148141 140 bytes

Returns a space-separated list of emirps in base b. (Could be 2 bytes shorter by returning a decimal list instead.)

f=(b,n,i=2)=>n?((p=(n,k=n)=>--k<2?k:n%k&&p(n,k))(i)&p(k=parseInt([...j=i.toString(b)].reverse().join,b))&&k-i&&n--?j+' ':'')+f(b,n,i+1):''


### Test cases

f=(b,n,i=2)=>n?((p=(n,k=n)=>--k<2?k:n%k&&p(n,k))(i)&p(k=parseInt([...j=i.toString(b)].reverse().join,b))&&k-i&&n--?j+' ':'')+f(b,n,i+1):''

console.log(f(2,10));
console.log(f(3,5));
console.log(f(12,7));
console.log(f(16,4));

# Python 2, 133 bytes

p=lambda n:all(n%i for i in range(2,n))
b,n=input()
i=b
while n:
j=i=i+1;r=0
while j:r=r*b+j%b;j/=b
if(i-r)*p(i)*p(r):print i;n-=1


Try it online!

Outputs each number on a new line, in base 10

# APL(NARS), 87 chars, 174 bytes

r←a f w;i
i←1⋄r←⍬
→2×⍳∼{∼0π⍵:0⋄k≡v←⌽k←{(a⍴⍨⌊1+a⍟⍵)⊤⍵}⍵:0⋄0πa⊥v:1⋄0}i+←1⋄r←r,i⋄→2×⍳w>≢r


The result will be in base 10. Test and results:

  3 f 1
5
2 f 10
11 13 23 29 37 41 43 47 53 61
3 f 5
5 7 11 19 31
12 f 7
17 61 67 71 89 137 151
16 f 4
23 31 53 59


{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵} would do conversion of ⍵ in base ⍺, array integer result; 0π⍵ would return true if ⍵ is prime else it would return 0.