20
\$\begingroup\$

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   ) 

...and in hexadecimal, they are:

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

\$\endgroup\$

11 Answers 11

6
\$\begingroup\$

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
 µ           - monadic chain separation
  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.

\$\endgroup\$
  • \$\begingroup\$ Congrats on winning! \$\endgroup\$ – FlipTack Nov 16 '16 at 17:29
8
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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)&
\$\endgroup\$
  • \$\begingroup\$ +1 IntegerReverse. Of course! Nice. \$\endgroup\$ – DavidC Jan 3 '17 at 16:06
  • \$\begingroup\$ 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]]& \$\endgroup\$ – Roman Jun 23 at 12:49
3
\$\begingroup\$

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@_[0];){}$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@_[0];){}
    $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.

\$\endgroup\$
3
\$\begingroup\$

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] *)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 232 214 191 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!

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

C, 293 286 261 bytes

Improved by @ceilingcat, 261 bytes:

v,t,i,j,c,g,s[9],r[9],b;main(n,a)int**a;{for(b=n=atoi(a[1]);g^atoi(a[2]);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[9],r[9],b=n=atoi(a[1]);x=atoi(a[2]);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!


My original answer, 293 bytes:

u,v,t,i,j,c,n,g;main(int x,char**a){char s[9],r[9],b=n=atoi(a[1]);x=atoi(a[2]);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.

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

JavaScript (ES6), 149 148 141 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));

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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[1] if is prime else it would return 0.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.