The Problem

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

The Solution

First, let's write a function to generate a series of 3 numbers that increases by 3330.

let series n = [n; n+3330;n+3330+3330]

Next, we need a function to determine if all elements in a list contain exactly the same digits.

let haveSameDigits l =

    let first::others = 
        l 
        |> List.map (fun x -> x.ToString())

    let containsChar (c : char) (s : string) =
        s.IndexOf(c) >= 0

    let rec haveSame (others : string list) =
        match others with
        | [] -> true
        | x::xs ->
            if (first |> Seq.forall (fun c -> containsChar c x)) then
                haveSame xs
            else
                false

    haveSame others

The haveSameDigits function takes a list l as input. It starts out by finding the first term in the list and separating it from all the others. Then it calls the internal haveSame function which checks all the values in others to see if each other element contains all the digits in first.

Now we need a way to determine if all the elements in a list are prime.

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 allArePrime l = 
    l |> List.forall isPrime

The allArePrime function returns true if all the elements in the input list l are prime. The functions intsqrt and isPrime are old friends from many other Euler problems.

Now we need a function to return a sequence of primes.

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

Again, the getPrimesBelow function is familiar if you've been following this series. We're going to use it to generate a sequence of 4-digit primes since we know from the problem definition that the value we're looking for has 4 digits.

For our last helper function, we need a simple way to concatenate together a list of integers, since that's the format required for the answer.

let listToString l = 
    System.String.Join("", l |> List.map (fun x -> x.ToString()))

Now we can solve the problem:

getPrimesBelow 10000
|> Seq.filter (fun n -> n > 1487)
|> Seq.map (fun n -> series n)
|> Seq.filter allArePrime
|> Seq.filter haveSameDigits
|> Seq.map listToString
|> Seq.head

We start by getting all primes below 10000 and then filtering out anything <= 1487. The problem definition gives us this starting point.

Next, we convert each element in the sequence into the series we're interested in. We filter out any of those series where not allArePrime and don't haveSameDigits.

And finally, we convert each element in the sequence to concatenated strings and return the head. That is the answer.

Other Posts in This Series