Introduction

Emirp primes are prime numbers that remain prime when the digits are reversed. For example, the prime number 13 is an emirp because its reversal is 31, which is also a prime number. This concept has applications in cryptography and computing. Emirp primes form an interesting subset of prime numbers and finding them can be a fun and engaging activity for people who are interested in prime numbers, algorithms and programming.

Implementation


(* Emirp primes *)

let int_reverse =
  let rec loop m n =
    if n < 10 then m + n else loop ((m + n mod 10) * 10) (n / 10)
  in loop 0

let is_prime n =
  let not_divisible x = n mod x <> 0 in
  seq_primes |> Seq.take_while (fun x -> x * x <= n) |> Seq.for_all not_divisible

let seq_emirps =
  let is_emirp n = let m = int_reverse n in m <> n && is_prime m in
  seq_primes |> Seq.filter is_emirp

let () =
  let seq_show sq = print_newline (Seq.iter (Printf.printf " %u") sq) in
  seq_emirps |> Seq.take 20 |> seq_show;
  seq_emirps |> Seq.drop_while ((>) 7700) |> Seq.take_while ((>) 8000) |> seq_show;
  seq_emirps |> Seq.drop 9999 |> Seq.take 1 |> seq_show

The implementation is written in the OCaml programming language. The code uses a pipeline of functions from the Seq module of the standard library to generate and filter prime numbers. The int_reverse function reverses the digits of an integer. The is_prime function checks if a given integer is prime or not. The seq_primes function generates an infinite sequence of prime numbers. The is_emirp function checks if a prime number is an emirp. The seq_emirps function generates an infinite sequence of emirp primes. The final expressions in the code print the 20 smallest emirps, the emirps in the range of 7700-8000 and the 10,000th emirp prime.

Step-by-step Explanation

  1. The int_reverse function is defined. It takes an integer as input, reverses its digits, and returns the reversed integer. This function is used later to check if a prime number is an emirp.

  2. The is_prime function takes an integer n as input and returns true if n is prime, false otherwise. It checks if n is divisible by any number less than or equal to the square root of n.

  3. The seq_primes function generates an infinite sequence of prime numbers using the Sieve of Eratosthenes algorithm. It starts with the first prime number 2 and generates the next prime number by checking if the numbers from 2 to sqrt(n) divide n. If none of those numbers divide n, then n is prime.

  4. The is_emirp function takes a prime number as input and checks if it is an emirp. It first reverses the digits of the prime number using the int_reverse function. If the reversed integer is different from the original integer and is also prime, then the input integer is an emirp.

  5. The seq_emirps function generates an infinite sequence of emirp primes by filtering the infinite sequence of prime numbers generated by seq_primes. It keeps only those prime numbers that are emirps.

  6. The final expressions in the code print the emirps generated by seq_emirps. The first expression prints the 20 smallest emirps. The second expression prints the emirps in the range of 7700-8000. The third expression prints the 10,000th emirp prime.

Complexity Analysis

  • The int_reverse function has time complexity O(log n) where n is the number of digits in the input integer. This is because the function reverses the integer digit by digit using modulo and division operations.

  • The is_prime function has time complexity O(sqrt(n)) where n is the input integer. This is because it checks if n is divisible by any number less than or equal to the square root of n.

  • The seq_primes function generates an infinite sequence of prime numbers using the Sieve of Eratosthenes algorithm. The time complexity of the Sieve of Eratosthenes algorithm is O(n log log n), where n is the upper bound of the range of numbers to be tested for primality. In this case, the range is infinite, so the upper bound is not known, but the sequence is generated lazily and only as needed, so only the prime numbers that are required are generated.

  • The is_emirp function has time complexity O(log n) + O(sqrt(n)), where n is the input prime number. This is because the int_reverse function has time complexity O(log n) and the is_prime function has time complexity O(sqrt(n)).

  • The seq_emirps function generates an infinite sequence of emirp primes by filtering the infinite sequence of prime numbers generated by seq_primes. The time complexity of the filtering operation is O(n log log n), where n is the number of prime numbers generated by seq_primes that are also emirps. However, since only a finite number of emirps are printed at the end, the actual time complexity is much lower. The sequence is generated lazily and only the required emirps are generated.

Overall, the implementation has good time complexity and uses efficient algorithms to generate and filter prime numbers and emirps.