17
\$\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\$
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\$
3
\$\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 2 days ago
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\$

C, 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.

New contributor
OverclockedSanic is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • \$\begingroup\$ @FlipTack You're right. I'll have to fix it tomorrow. \$\endgroup\$ – OverclockedSanic 2 days ago
  • \$\begingroup\$ @FlipTack Fixed and tested to make sure it passes your tests. Is this good? \$\endgroup\$ – OverclockedSanic yesterday
  • \$\begingroup\$ Sure is! And welcome to code golf. \$\endgroup\$ – FlipTack yesterday
  • \$\begingroup\$ Nice work! I moved some increment operators to get you down to 286 \$\endgroup\$ – movatica 2 hours ago
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 3, 232 214 191 bytes

Credit to Herman L for 14 bytes and the lead to more improvement!

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]
  if(c!=d)*p(i)*p(int(d,b)):l+=[c];n-=1
 return l

Try it online!

Unfortunately there is neither a builtin primecheck, nor a int2str conversion with variable base. Both cost quite a few bytes.

While this was not taken from the reference code, it became kind of a golfed version of it.

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

Runic Enchantments, 91 bytes (non-competing)

{:"i:::'PA?;r͍:'PA?;=?;@"E͍1K1K{{B͍
0T:1)a*?e2*2';w;>i1-
1I2+1K1K1K1K1K2?>d00Bl1=6*?$',$

Try it online!

Runic doesn't have a way to do base conversions built in, but I was intrigued with the core concept of identifying emirps, so I did what I could to answer the challenge in only base 10. Hence non-competing.

Converting to and from an arbitrary base is difficult due to the stack management involved (it takes 62 bytes to convert from decimal to an arbitrary base in string representation while assuming no other values are on the stack; converting back would take about the same). Under ideal conditions, inserting these methods as 'functions' (own length plus knowable overhead) would result in a total of 239 bytes. It would be more, due to the location that the calls would need to be made (either side of , which is not raw code, but a string that is run through Eval). And dealing with that mess is not fun for me.

Explanation

Validating an input value as a emirp was pretty easy:

i:::'PA?;r͍:'PA?;=?;@

Take input, is it prime? Reverse it, is it prime? Are those two values distinct? Output.

I probably could have run that part without using Eval, but discarding the unneeded ToS copies gets tricky so the 18 byte cost is probably worth it; all of the 1K pairs are to replenish the IP's energy after spending a good portion of it on the Eval command (else the program terminates early). They are split across lines just to make the program more compact, which saves a few bytes in the skip-over instructions when an emirp isn't found.

The IP that is created on the second line tracks how many emirps have been located, while the IP created on the third line looks for emirps (starting at 13, as smaller values are known invalid and incrementing by 2).

The 1IT sequence handles making the first IP wait for a result from the second before decrementing the input (1st IP waits, 2nd IP forks an IP upwards to cause the 1st to resume).

e2*2';w; causes program termination by overwriting the ' with a ; at the end of line 3 (outputting the last value but not outputing a trailing ,).

Note:

There was a bug in my primailty check instruction and discovered as a result of this challenge and as soon as Dennis rebuilds the TIO executable values such as 19 and 91 won't be incorrectly identified as emirps.

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