Edit

Emirp

Challenge: Reversible Primes

A prime number is a number that is only divisible by 1 and itself, for example, 7. An emirp is a prime number that results in a different prime when its decimal digits are reversed. For example, 107 and 701 are a pair of emirps, and 3,049 and 9,403.

Palindromic numbers are not emirps. 101 is a prime and its reverse is itself -- it is not an emirp.

Your task for this challenge is write a generator that will add up all the first n emirps. To be precise, you should write a generator emirp which takes a @ud number n as an input, and returns a @ud number which is the sum of the first n emirps.

Example usage:

> +emirp 10
638

The first 10 emirps are 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, and their sum is 638.

Solutions

These solutions were submitted by the Urbit community as part of a competition in ~2024.3. They are made available under the MIT License and CC0. We ask you to acknowledge authorship should you utilize these elsewhere.

Solution #1

By ~nodmel-todsyr. A very fast and efficient solution.

::  emirp.hoon
::  Finds a sum of first n emirp numbers
|^
|=  [n=@ud]
=/  i  0
=/  sum  0
=/  number  13
=|  emirps=(set @ud)
|-
?:  =(i n)
  sum
=^  x=@ud  emirps  (find-emirp number emirps)
%=  $
  i  +(i)
  sum  (add sum x)
  :: iterating only over 6k +- 1 numbers
  number  (add ?:(=((mod x 6) 1) 4 2) x)
==
::  Finds a smallest emirp which is greater than or equal to x.
::  Adds flipped emirp to the set of emirps
::  If emirp is in the set, returns it immediately
::
++  find-emirp
  |=  [x=@ud emirps=(set @ud)]
  ^-  [@ud (set @ud)]
  =/  flipped  (flip x)
  ?:  (~(has in emirps) x)
    [x emirps]
  ?:  &(!=(x flipped) (is-prime x) (is-prime flipped))
    [x (~(put in emirps) flipped)]
  $(x (add ?:(=((mod x 6) 1) 4 2) x))
::  Checks if x is a prime. 
::
++  is-prime
  |=  [x=@ud]
  ^-  ?
  ?:  (lte x 3)
    (gth x 1)
  ?:  |(=((mod x 2) 0) =((mod x 3) 0))
    %.n
  =/  limit  p:(sqt x)
  =/  j  5
  |-
  ?:  (gth j limit)
    %.y
  ?:  |(=((mod x j) 0) =((mod x (add 2 j)) 0))
    %.n
  $(j (add j 6))
::  Flips a number.
::
++  flip
  |=  [number=@ud]
  ^-  @ud
  =/  m  0
  =/  rip  (curr div 10)
  =/  last  (curr mod 10)
  |-
  ?:  =(number 0)
    m
  %=  $
    number  (rip number)
    m  (add (mul 10 m) (last number))
  ==
--

Solution #2

By ~ramteb-tinmut. Well-commented, easy to read, and fast.

Unit Tests

Following a principle of test-driven development, the unit tests below allow us to check for expected behavior. To run the tests yourself, follow the instructions in the Unit Tests section.

PreviousCompetitive ProgrammingNextGleichniszahlenreihe

Last updated