theburningmonk.com

Prob­lem

We shall say that an n-digit num­ber is pandig­i­tal if it makes use of all the dig­its 1 to n exactly once. For exam­ple, 2143 is a 4-digit pandig­i­tal and is also prime.

What is the largest n-digit pandig­i­tal prime that exists?

Solu­tion

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 hasDivisor(n) =
    let upperBound = int64(sqrt(double(n)))
    [2L..upperBound] |> Seq.exists (fun x -> n % x = 0L)
let isPrime(n) = if n = 1L then false else not(hasDivisor(n))

let answer =
    [1..9]
    |> List.collect (fun m -> [1..m] |> permute)
    |> List.map (fun l -> l |> List.map string |> List.reduce (fun acc item -> acc + item))
    |> List.map int64
    |> List.filter isPrime
    |> List.max

This is a sim­ple brute force solu­tion which for n = 1..9 gen­er­ates all per­mu­ta­tions of 1..n, for each per­mu­ta­tion the dig­its are merged into a num­ber, e.g. [1; 4; 8; 7] –> 1487, and the max prime num­ber is returned.