Emirp primes: Difference between revisions

 

An   ''emirp''   ('''prime''' spelled backwards)   are primes that when reversed   (in their decimal representation)   are a different prime.

*   [https://oeis.org/A006567 The On‑Line Encyclopedia of Integer Sequences, emirps (A6567)].

<br><br>

 

=={{header|Ada}}==

he solution uses the package Miller_Rabin from the [[Miller-Rabin primality test]].

 

 

procedure Emirp_Gen is

end loop;

Ada.Text_IO.Put_Line(Num'Image(Current));

 

{{out}}

Uses Algol 68G specific argc and argv procedures to access to command line.

Allows the user to specify the from and to range values or ordinals on the command line. The sieve size can also be specified. As suggested by the Fortran sample, from = to is treated as a special case for labeling the output.

INT emirp from := 1; # lowest emirp required #

INT emirp to := 10; # highest emirp required #

 

# construct a sieve of primes up to the maximum number required for the task #

 

# return TRUE if p is an emirp, FALSE otherwise #

OD

FI;

{{out}}

a68g emirpPrimes.a68 - FROM 1 TO 20

emirp 10000: 948349

</pre>

 

=={{header|AutoHotkey}}==

p := 1

Loop, 20 {

r := A_LoopField r

return r

{{Output}}

<pre>First twenty emirps: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

 

cat emirp.awk

function is_prime(n, p)

{

printf("\n")

}

{{Output}}

<pre>

948349

</pre>

 

=={{header|C}}==

Note the unusual commandline argument parsing to sastisfy the "invoke three times" magic requirement.

 

typedef unsigned uint;

putchar('\n');

return 0;

{{out}}

<pre>

</pre>

 

{{works with|C sharp|7}}

using System;

using System.Linq;

return reverse;

}

{{out}}

<pre>

10000th:

948349

</pre>

 

===Using biginteger's isProbablePrime()===

The isProbablePrime() method performs a Miller-Rabin primality test to within a given certainty.

(let [a (biginteger v)

b (biginteger (clojure.string/reverse (str v)))]

(println "10,000: " (nth (filter emirp? (iterate inc 0)) 9999))

 

{{out}}

<pre>first20: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

10,000: 948349

</pre>

 

=={{header|D}}==

bool isPrime(in uint n) pure nothrow @nogc {

if (n == 2 || n == 3)

iota(7_700, 8_001).filter!isEmirp);

writeln("10000th: ", uints.filter!isEmirp.drop(9_999).front);

{{out}}

<pre>First 20:

 

===Sieve-Based Version===

 

/// Not extendible Sieve of Eratosthenes.

iota(7_700, 8_001).filter!isEmirp);

writeln("10000th: ", uints.filter!isEmirp.drop(9_999).front);

The output is the same. With ldc2 compiler the run-time is about 0.06 seconds.

 

=={{header|Elixir}}==

defp prime?(2), do: true

defp prime?(n) when n<2 or rem(n,2)==0, do: false

end

 

 

{{out}}

=={{header|F_Sharp|F#}}==

===The function===

// Generate emirps. Nigel Galloway: November 19th., 2017

let emirp =

let rec fN n g = match n with |0->g |_->fN (n/10) (g*10+n%10)

let fG n g = n<>g && isPrime g

===The Task===

emirps |> (Seq.take 20) |> Seq.iter (printf "%d ")

{{out}}

<pre>

13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

</pre>

emirps |> Seq.skipWhile (fun n->n<7700) |> Seq.takeWhile (fun n->n<=8000) |> Seq.iter (printf "%d ")

{{out}}

<pre>

7717 7757 7817 7841 7867 7879 7901 7927 7949 7951 7963

</pre>

printfn "%d" (Seq.item 9999 emirps)

{{out}}

<pre>

948349

</pre>

// count # of emirps with n = 2 to 7 digits. Nigel Galloway: August 8th., 2018

let n=emirp |> Seq.takeWhile(fun n->n<10000000) |> Seq.countBy(fun n->match n with |n when n>999999->7

|_ ->2)

for n,g in n do printfn "%d -> %d" n g

{{out}}

<pre>

 

=={{header|Factor}}==

math.primes sequences ;

FROM: prettyprint => . pprint ;

part1 nl part2 nl part3 ;

{{out}}

<pre>

10,000th emirp:

948349

</pre>

 

For factoring numbers up to the 32-bit two's complement integer limit, the table need not be large, and it can easily enough be stored as a collection of sixteen and thirty-two bit numbers to save some space. Accessing an array PRIME(i) can be made a function GETPRIME(i) without a change in syntax (as needed in pascal: Prime[i] for an array, GetPrime(i) for a function), at least for reading. So, instead of 4792x4 = 19168 bytes, 12144 are needed, to set against the additional code complexity. These days, this is a difference of small importance. Actually, a further value is needed to hold Prime(4793) = 46349. Function ISPRIME does not determine its stepping point via the near universal usage of SQRT(n). If calculated in double precision this will give acceptable results for a 32-bit integer, but I have been burnt by an ad-hoc calculation nDgits = LOG10(x) + 1 failing for x = 10 because Log10(10) = 0·9999etc. which may well round to one, but truncates to zero. So, a SQRT-free demonstration, needed if the MOD function were unavailable. Actually, if P(i) is the last factor to be checked, this suffices up to the square of P(i + 1), not P(i). But this bound is only useful when successive numbers are being tested; for an individual factorisation it is too messy.

 

INTEGER MSG !I/O unit number to share about.

INTEGER PF16LIMIT,PF32LIMIT,NP !Know that P(3512) = 32749, the last within two's complement 16-bit integers.

CALL EMIRP(10,10000,10000, 1,1000000) !Of three separate invocations.

 

Output:

<pre>

 

=={{header|FreeBASIC}}==

 

Function isPrime(n As UInteger) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

The 10,000th Emirp prime is : 948349

</pre>

 

=={{header|Go}}==

 

As a side note, by using the same API as the prime number generator this also demonstrates how Go interfaces can be used (and note it doesn't require the existing code/package to know anything about the interface being defined).

 

import (

fmt.Println()

}

{{out}}

<pre>

948349

</pre>

 

=={{header|Haskell}}==

{{Works with|primes|0.2.1.0}}

 

 

import Data.HashSet (HashSet, fromList, member)

"slice" -> print $ emirpSlice lo hi

"values" -> print $ emirpValues lo hi

 

{{out}}

 

<pre>

===List-based===

Using list-based incremental sieve from [[Sieve_of_Eratosthenes#With_Wheel|here]] and trial division from [[Primality_by_trial_division#Haskell|here]],

 

λ> take 20 . filter emirp $ primesW

 

λ> (!! (10000-1)) . filter emirp $ primesW

 

=={{header|J}}==

 

 

In other words: select numbers from the argument list whose decimal reverse is both different and prime and return those decimal reversed values as numbers. (For simplicity, we require that our argument be a list of prime numbers.)

 

13 17 31 37 71 73 79 97 113 311 701 733 743 751 761 941 953 971 983 991

 

NB. alternative approach (first emirp value would be at index 0):

9999 { /:~ emirp p:i.1e5

 

=={{header|Java}}==

This implementation uses a slight optimization discussed in the talk page. It will not actually check the primality (forwards or backwards) for a number that starts or ends with the digits 2, 4, 5, 6, or 8 since no primes greater than 7 end with those digits.

//trivial prime algorithm, sub in whatever algorithm you want

System.out.println(--x);

}

{{out}}

<pre>First 20 emirps:

7717 7757 7817 7841 7867 7879 7901 7927 7949 7951 7963

10,000th emirp:

948349</pre>

 

 

'''Infrastructure: prime numbers'''

if . == 2 then true

else

| until( relatively_prime ; .[0] += 2) as $nextp

| ( $previous + [$nextp[0]] );

 

'''Emirps'''

. as $n

| tostring | explode | reverse | implode | tonumber | (. != $n) and is_prime ;

else if ($p | is_emirp) then [.[0] + 1, $p] else .[1] = null end

end;

 

'''The tasks'''

 

(0) The three separate subtasks can be accomplished in one step as follows:

 

The output of the above is shown below.

 

(1) First twenty:

 

(2) Selection by value

| primes

| if (7700 <= .) and (. <= 8000) and is_emirp then .

elif . > 8000 then break $top

else empty

 

(3) 10,000th

 

{{out}}

[1,13]

[2,17]

[189,7951]

[190,7963]

 

=={{header|Julia}}==

 

function collapse(n::Array{<:Integer})

 

Base.reverse(n::Integer) = collapse(reverse(digits(n)))

 

function firstnemirps(m::Integer)

i, n = 1, 2

if isemirp(n)

rst[i] = n

println("First 20:\n", emirps[1:20])

println("Between 7700 and 8000:\n", filter(x -> 7700 ≤ x ≤ 8000, emirps))

Between 7700 and 8000:

[7717, 7757, 7817, 7841, 7867, 7879, 7901, 7927, 7949, 7951, 7963]

10000th:

 

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun isPrime(n: Int) : Boolean {

while(true)

print(i)

 

{{out}}

The 10,000th Emirp prime is : 948349

</pre>

 

=={{header|Lua}}==

function isPrime (n)

if n < 2 then return false end

print("Wrong number of arguments")

end

Command prompt session:

<pre>

 

=={{header|Maple}}==

local eprime;

eprime := parse(StringTools:-Reverse(convert(n,string)));

EmirpPrime~([seq(7700..8000)]);

EmirpsList(10000)[-1];

{{out}}

<pre>[13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389]

948349</pre>

 

First a simple helper function

A function to test whether n is an emirp prime

Note, this test function assumes n is prime. Adding a check to verify n is prime will have

an impact on execution time for finding the mth emirp prime particularly when m is large.

 

Finally, a function which returns the first emirp prime larger than the supplied argument

 

With these the first 20 emirp primes are computed as:

{{out}}

<pre>

 

The emirp primes betweewn 7700 and 8000 are:

{{out}}

<pre>

 

The 10,000th emirp prime is:

{{out}}

<pre>

 

=={{header|MATLAB}}==

NN=(1:1:1e6); %Natural numbers between 1 and t

pns=NN(isprime(NN)); %prime numbers

a=pns(isprime(p)); b=p(isprime(p)); c=a-b;

emirps=NN(a(c~=0));

{{out}}

<pre>the first twenty emirps are: emirps(1:20)

948349

</pre>

=={{header|Modula-2}}==

FROM Conversions IMPORT StrToLong;

FROM FormatString IMPORT FormatString;

 

ReadChar

 

 

Using isPrime function of Primality by trial division task :

 

n isPrime ifFalse: [ false return ]

n asString reverse asInteger dup n == ifTrue: [ drop false ] else: [ isPrime ] ;

dup isEmirp ifTrue: [ dup l add ] 1 +

]

 

{{out}}

 

=={{header|PARI/GP}}==

emirp(n)=my(r=rev(n)); isprime(r) && isprime(n) && n!=r

select(emirp, primes(100))[1..20]

select(emirp, primes([7700,8000]))

{{out}}

<pre>%1 = [13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389]

using trial division unit , but jumping over number ranges, where the reversed numbers can't be a prime.

Compiles with Delphi and Free Pascal.

//palindrome prime 13 <-> 31

{$IFDEF FPC}

OutPutHelp;

end;

;output:

<pre>

=={{header|Perl}}==

{{libheader|ntheory}}

use ntheory qw(forprimes is_prime);

 

forprimes { print " $_" if is_prime(reverse $_) && $_ ne reverse($_) } 7700,8000;

print "\n";

{{out}}

<pre>First 20: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

The 10_000'th emirp: 948349</pre>

 

 

 

 

}

}

}

 

 

 

 

 

=={{header|PicoLisp}}==

(and

(bit? 1 N)

(println (take1 20))

(println (take2))

{{out}}

<pre>(13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389)

 

=={{header|PL/I}}==

pt1: Proc(run) Options(main);

/*********************************************************************

End;

 

 

{{out}}

 

There is no explicit hard-coded ceiling added to the code for the prime generator, which is the reason given for the need to invoke a program three times in the task description.

from prime_decomposition import primes, is_prime

from heapq import *

if pr >= 7700: print(pr, end=', ')

print(']')

 

{{out}}

10000th:

[948349]</pre>

 

=={{header|Racket}}==

basic functions, unburdened by accounting or (too many) performance

considerations (please don't mark this as needing attention... I know it falls short of

(require math/number-theory)

 

(let loop ((i 10000) (p 9))

(define p+2 (+ p 2))

 

The second is somewhat larger and seems to be a playground for all sorts of code.

;; ---------------------------------------------------------------------------------------------------

;; There are two distinct requirements here...

(check-equal? (time (task2 emirp-prime?/sieve)) (time (task2)))

(check-equal? (time (task3 emirp-prime?/sieve extend-sieve!)) (time (task3))))

 

{{out}}

948349

Sieve size: 999998</pre>

 

=={{header|REXX}}==

<br>memoization was added (assisting with the <big>√{{overline|&nbsp;j&nbsp;}}</big>), &nbsp; and some of the trial divisions were hard-coded to minimize

<br>the CPU time a bit.

parse arg x y . /*obtain optional arguments from the CL*/

if x=='' | x=="," then do; x=1; y=20; end /*Not specified? Then use the default.*/

/* [↓] display the emirp list. */

say strip($); say; n=words($); ?=(n\==1) /*display the emirp primes wanted. */

'''output''' &nbsp; when using the following for input: &nbsp; <tt> 1 &nbsp; 20 </tt>

<pre>

 

===version 2===

* 27.03.2014 Walter Pachl

*********************************************************************/

Say l

End

'''output'''<pre>rexx ptz 1

the first 20 emirps:

 

=={{header|Ring}}==

nr = 1

m = 2

next

return true

 

=={{header|Ruby}}==

 

emirp = Enumerator.new do |y|

break

end

 

{{out}}

 

=={{header|Rust}}==

 

extern crate primal;

println!("Emirps-s between 7700 and 8000 : {:?}", vec2);

println!("10.000-th emirp : {}", emirp_10_000);

{{out}}

<pre>

===Using BigInt's isProbablePrime()===

The isProbablePrime() method performs a Miller-Rabin primality test to within a given certainty.

val b = BigInt(v.toLong)

val r = BigInt(v.toString.reverse.toLong)

println( "%32s".format( "Emirps between %d and %d: ".format( b1, b2 )) + {for( i <- b1 to b2 if( isEmirp(i) ) ) yield i}.mkString(",") )

println( "%32s".format( "%,d emirp: ".format( c )) + Iterator.from(2).filter( isEmirp(_) ).drop(c-1).next )

{{out}}

<pre> First 20 emirps: 13,17,31,37,71,73,79,97,107,113,149,157,167,179,199,311,337,347,359,389

Emirps between 7700 and 8000: 7717,7757,7817,7841,7867,7879,7901,7927,7949,7951,7963

10,000 emirp: 948349</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

for (var p = a.dec.next_prime; p <= b; p.next_prime!) {

callback(p)

forprimes(7700, 8000, {|p| is_emirp(p) && take(p) })

}.join(' '))

{{out}}

<pre>

The 10,000'th emirp: 948349

</pre>

=={{header|Smalltalk}}==

Works with Smalltalk/X

 

First an emirp checker:

[:p | |e|

(e := p asString reversed asNumber) isPrime

and:[ e ~= p ]

 

an infinite list of primes:

[:n |

LazyCons car:n cdr:[primeGen value:(n nextPrime)]

 

an infinite list of emirps, taking an infinite list of primes as arg:

[:l | |rest el|

rest := l.

[ el := rest car. rest := rest cdr. isEmirp value:el ] whileFalse.

LazyCons car:el cdr:[emirpGen value:rest]

two infinite lists:

generating output:

show:'first 20 emirps: ';

showCR:(listOfEmirps take:20) asArray.

Transcript

show:'10000''th emirp: ';

 

Generates:<pre>

 

LazyCons is easily defined as:

car:newCar cdr:newCdr

car := newCar. cdr := newCdr

cdr := cdr value.

self changeClassTo:Cons.

 

=={{header|Stata}}==

 

list in 1/20, noobs noh

 

+--------+

| 948349 |

 

Now the definition of ''emirp.ado'':

 

args n

qui clear

st_store(.,1,a)

}

 

=={{header|Tcl}}==

{{tcllib|math::numtheory}}

 

# Import only to keep line lengths down

if {[emirp? $n] && [incr ne] == 10000} break

}

{{out}}

<pre>

10,000: 948349

</pre>

 

=={{header|VBA}}==

 

 

Private Const MAX As Long = 5000000

On Error GoTo 0

End If

{{out}}

<pre>At this point : Execution time = 13,23047 seconds.

all emirps between 7,700 and 8,000: 7717, 7757, 7817, 7841, 7867, 7879, 7901, 7927, 7949, 7951, 7963

the 10,000th emirp: 948349</pre>

 

=={{header|zkl}}==

Uses the solution from task [[Extensible prime generator#zkl]]. Saves the primes to a list, which gets pretty big.

var ps=Utils.Generator(PS), plist=ps.walk(10).copy();

 

Utils.Generator(PS).filter(fcn(p){if(p>8000)return(Void.Stop); p>7700 and isEmirp(p)});

 

{{out}}

<pre>