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