### 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 * 10place, 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