# Project Euler – Problem 49 Solution

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

#### Solution

```open System.Collections

let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
| [] -> [[]]
| e::xs -> List.collect (distribute e) (permute xs)

let rec comb n l =
match n, l with
| 0, _ -> [[]]
| _, [] -> []
| k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs

let max = 9999

// define a cache for holding records of which number is a prime
let cache = new BitArray(max+1, true)

// using prime sieve to fill out the cache
[2..max]
|> List.iter (fun n ->
if cache.[n] then
[2..max]
|> Seq.takeWhile (fun m -> n * m <= max)
|> Seq.iter (fun m -> cache.[n * m]  List.filter (fun n -> cache.[n])

// define function to get the 4-digit prime permutations of a number
let getPrimePermutations n =
let digitsStr = n.ToString().ToCharArray() |> Array.map string
Array.toList digitsStr
|> permute
|> Seq.distinct
|> Seq.map (fun chars -> int(chars |> List.reduce (+)))
|> Seq.filter (fun x -> x >= 1000 && cache.[x])
|> Seq.sort
|> Seq.toList

|> List.map getPrimePermutations
|> List.filter (fun l -> l |> List.length >= 3)
|> Seq.distinct
|> Seq.toList
|> List.map (fun l -> comb 3 l |> List.filter (fun l' -> l'. - l'. = l'. - l'.))
|> List.filter (fun l -> l |> List.length > 0)
```

The above solution returns two lists:

val answer : int list list list = [[[1487; 4817; 8147]]; [[2969; 6299; 9629]]]

The first of course, correlates to the example given in the brief, the other, is the base for your answer!