The Problem

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

The Solution

So, this seems straightforward enough. We need to take the digits 1..9 and generate all possible combinations of them and then determine if they are prime or not.

We'll start with a pair of functions I got from this Stack Overflow question. I use these functions over and over again, and not just for solving Project Euler problems. I have these in lots of production code. They are super useful. Thank you Jon Harrop.

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)

The distribute function distributes a value e across all possible locations in a list. So, if you execute distribute 1 [2; 3] you get:

• [1; 2; 3]
• [2; 1; 3]
• [2; 3; 1]

The permute function recursively loops through each item in the input and uses distribute to distribute that element through all positions. So if you execute permute [1; 2; 3] you get:

• [1; 2; 3]
• [2; 1; 3]
• [2; 3; 1]
• [1; 3; 2]
• [3; 1; 2]
• [3; 2; 1]

That's great, but in addition to all the permutations of a list [1..n] we also need the permutations of [1..n-1] and [1..n-2] and so on.

let getPermutations l =
    l |> List.collect (fun e -> [1..e] |> permute)

The getPermutations function takes a list and, for each element e in the list, generates a new list [1..e] and all of its permutations.

Next, we'll steal some code from another problem for determing if a 64-bit number is prime.

let int64sqrt (i : int64) = int64(sqrt(float i))

let isPrime64 (i : int64)  =
    if i <= 1L then false
    elif i = 2L then true
    elif (i &&& 1L) = 0L then false
    else
        let sr = int64sqrt i
        seq { 3L..2L..sr } |> Seq.forall (fun f -> i%f<>0L)

And now we can solve the problem:

[1..9]
|> getPermutations
|> List.map (fun l -> System.String.Join("", l |> List.map string))
|> List.map int64
|> List.filter isPrime64
|> List.max

The code above generates all permutations of [1..9], turns those lists into strings, converts those strings to 64-bit integers, and filters out anything that isn't prime. The maximum value of the resulting list is the answer.

Other Posts in This Series