Project Euler — Problem 35 Solution

Problem

The num­ber, 197, is called a cir­cu­lar prime because all rota­tions of the dig­its: 197, 971, and 719, are them­selves prime.

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

How many cir­cu­lar primes are there below one mil­lion?

Solution

open System

let hasDivisor(n:bigint) =
    let upperBound = bigint(sqrt(double(n)))
    [2I..upperBound] |> Seq.exists (fun x -> n % x = 0I)

let isPrime(n:bigint) = if n = 1I then false else not(hasDivisor(n))

let rotate(n:bigint) =
    let charList =n.ToString().ToCharArray() |> Array.toList
    let len = List.length charList
    [0..(len-1)]
    |> List.map (fun r -> List.permute (fun i -> (i + r) % len) charList)
    |> List.map (fun l -> String.Join("", l |> List.toArray))
    |> List.map bigint.Parse

let isCircularPrime(n:bigint) = rotate n |> List.forall isPrime

let answer = [2I..999999I] |> Seq.filter isPrime |> Seq.filter isCircularPrime |> Seq.length

The rotate func­tion uti­lizes the List.permute func­tion to rotate the ele­ments in the char array rep­re­sen­ta­tion of a giv­en num­ber, the rest is all pret­ty straight for­ward.

It’s worth not­ing that this is a brute force approach and does take quite a bit of time to run, but is also the most sim­ple and eas­i­ly under­stood solu­tion. In the forum thread for the prob­lem there are many sug­ges­tions for opti­miza­tions, and indeed many peo­ple have man­aged to write code which runs under a sec­ond! Also, you can improve on the per­for­mance of my solu­tion huge­ly if you just cache some of the com­put­ed results (e.g. has­Di­vi­sor is a great place to start) with a dic­tio­nary.