15
\$\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\$
5
\$\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\$
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\$

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
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\$

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.