The Problem

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

The Solution

Well, it seems like just a couple of days ago we were writing functions to generate primes below a certain number. Let's copy those here:

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

Now we'll start focusing on the problem by determining if a number is a "truncatable prime" starting from the left.

let isTruncatablePrimeLeft n =
    let rec isTruncatable s =
        match s with
        | "" -> true
        | _ ->
            if isPrime (int(s)) then isTruncatable (s.Substring(1))
            else false
    isTruncatable n

The function above recurses over and over, chopping off the left digit each time, and checks to see if the resulting number is prime. If we get to an empty string, then all previous numbers have been prime and we return true.

let isTruncatablePrimeRight n =
    let rec isTruncatable s =
        match s with
        | "" -> true
        | _ ->
            if isPrime (int(s)) then isTruncatable (s.Substring(0, s.Length - 1))
            else false
    isTruncatable n

isTruncatablePrimeRight works the same way, except it truncates characters from the right.

And now we can solve the problem:

let isTruncatablePrime n = (isTruncatablePrimeLeft n) && (isTruncatablePrimeRight n)

getPrimesBelow 1000000
|> Seq.filter (fun x -> x >= 11)
|> Seq.filter (fun x -> isTruncatablePrime (x.ToString()))
|> Seq.take 11
|> Seq.sum

We combine the left and right tests into a single function called isTruncatablePrime.

Then it's a simple matter of generating the sequence of primes and testing it.

Other Posts in This Series