Definitions
A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will also be prime.

For example:
1193 is a circular prime, since 1931, 9311 and 3119 are all also prime.

Note that a number which is a cyclic permutation of a smaller circular prime is not considered to be itself a circular prime. So 13 is a circular prime, but 31 is not.



A repunit (denoted by R) is a number whose base 10 representation contains only the digit 1.

For example:
R(2) = 11 and R(5) = 11111 are repunits.



Task
 Find the first 19 circular primes.


 If your language has access to arbitrary precision integer arithmetic, given that they are all repunits, find the next 4 circular primes.


 (Stretch) Determine which of the following repunits are probably circular primes: R(5003), R(9887), R(15073), R(25031), R(35317) and R(49081). The larger ones may take a long time to process so just do as many as you reasonably can.


See also
 Wikipedia article - Circular primes.
 Wikipedia article - Repunit.
 OEIS sequence A016114 - Circular primes.


package main
 
import (
    "fmt"
    big "github.com/ncw/gmp"
    "strings"
)
 
// OK for 'small' numbers.
func isPrime(n int) bool {
    switch {
    case n < 2:
        return false
    case n%2 == 0:
        return n == 2
    case n%3 == 0:
        return n == 3
    default:
        d := 5
        for d*d <= n {
            if n%d == 0 {
                return false
            }
            d += 2
            if n%d == 0 {
                return false
            }
            d += 4
        }
        return true
    }
}
 
func repunit(n int) *big.Int {
    ones := strings.Repeat("1", n)
    b, _ := new(big.Int).SetString(ones, 10)
    return b
}
 
var circs = []int{}
 
// binary search is overkill for a small number of elements
func alreadyFound(n int) bool {
    for _, i := range circs {
        if i == n {
            return true
        }
    }
    return false
}
 
func isCircular(n int) bool {
    nn := n
    pow := 1 // will eventually contain 10 ^ d where d is number of digits in n
    for nn > 0 {
        pow *= 10
        nn /= 10
    }
    nn = n
    for {
        nn *= 10
        f := nn / pow // first digit
        nn += f * (1 - pow)
        if alreadyFound(nn) {
            return false
        }
        if nn == n {
            break
        }
        if !isPrime(nn) {
            return false
        }
    }
    return true
}
 
func main() {
    fmt.Println("The first 19 circular primes are:")
    digits := [4]int{1, 3, 7, 9}
    q := []int{1, 2, 3, 5, 7, 9}  // queue the numbers to be examined
    fq := []int{1, 2, 3, 5, 7, 9} // also queue the corresponding first digits
    count := 0
    for {
        f := q[0]   // peek first element
        fd := fq[0] // peek first digit
        if isPrime(f) && isCircular(f) {
            circs = append(circs, f)
            count++
            if count == 19 {
                break
            }
        }
        copy(q, q[1:])   // pop first element
        q = q[:len(q)-1] // reduce length by 1
        copy(fq, fq[1:]) // ditto for first digit queue
        fq = fq[:len(fq)-1]
        if f == 2 || f == 5 { // if digits > 1 can't contain a 2 or 5
            continue
        }
        // add numbers with one more digit to queue
        // only numbers whose last digit >= first digit need be added
        for _, d := range digits {
            if d >= fd {
                q = append(q, f*10+d)
                fq = append(fq, fd)
            }
        }
    }
    fmt.Println(circs)
    fmt.Println("\nThe next 4 circular primes, in repunit format, are:")
    count = 0
    var rus []string
    for i := 7; count < 4; i++ {
        if repunit(i).ProbablyPrime(10) {
            count++
            rus = append(rus, fmt.Sprintf("R(%d)", i))
        }
    }
    fmt.Println(rus)
    fmt.Println("\nThe following repunits are probably circular primes:")
    for _, i := range []int{5003, 9887, 15073, 25031, 35317, 49081} {
        fmt.Printf("R(%-5d) : %t\n", i, repunit(i).ProbablyPrime(10))
    }
}