The Problem

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

The Solution

We'll start with some helper functions that we've used over and over again in this series. We need to turn a string into a sequence of digits, and generate a sequence of primes below 1 million.

let digitize n =
    let str = sprintf "%i" n
    str |> Seq.map (fun x -> int(x) - int('0'))

let intsqrt i = int(sqrt(float i))

let isPrime i =
    if i <= 1 then false
    elif i = 2 then true
    elif (i &&& 1) = 0 then false
    else
        let sr = intsqrt i
        seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime x =
    match x with
    | x when isPrime x -> x
    | x -> nextPrime (x + 1)

let getPrimesBelow max =
    let primeGenerator candidate =
        if candidate > max then
            None
        elif candidate = 2 then
            Some(2,3)
        else
            let next = nextPrime candidate
            if next >= max then
                None
            else
                Some(next,next+2)

    Seq.unfold primeGenerator 2

We've covered all this ground before. In Problem 3, for example. So, I won't go into the details of these functions.

Next, we need to figure out how to generate all the rotations of a number.

let rotate step l =
    let l1,l2 = l |> List.splitAt step
    List.append l2 l1

let toNumber (l : int list) =
    l
    |> Seq.rev
    |> Seq.mapi (fun place d -> d * (pown 10 place))
    |> Seq.sum

let rotationsOf n = 
    let digits = digitize n |> List.ofSeq
    [for i in 1..((List.length digits) - 1) -> digits |> rotate i] |> List.map toNumber

The rotate function takes as input an integer step and a list of digits. It uses List.splitAt to break the list into two chunks, and then uses List.append to generate a new list with the second chunk at the front. So, using the problem's example of 197, we can get the other 2 rotations as follows:

rotate 1 [1; 9; 7] = [9; 7; 1]
rotate 2 [1; 9; 7] = [7; 1; 9]

The toNumber function takes a list of digits and turns them back into a number. It does this by reversing the order of the list, mapping each element in the list to d * 10^place, and them summing the result. Some experimenting I did later shows that it is just as fast, if not faster, to convert the digits to a string and then use the built-in CLR functions for converting string to int, but this way is more fun so I left it as-is.

Now, we can figure out if a given number is a circular prime.

let isCircularPrime n =
    rotationsOf n
    |> List.forall isPrime

isCircularPrime tests all rotations of n to see if they are prime and returns true if they are. We don't need to test n itself because we already know it's prime. Testing primes is computationally expensive, so eliminating that one redundant check reduces program execution time by almost 30%.

And now we can get the answer:

#time
getPrimesBelow 1000000
|> Seq.filter isCircularPrime
|> Seq.length
#time

We generate a sequence of all primes below one million, filter out the ones that aren't circular, and return the length of the resulting sequence, which is the answer.

Other Posts in This Series