## 60 Days of Euler in F# - Problem 49

### 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.