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

My first approach was to try and find the first odd number descending from 987654321 which was both prime and pandigital, but despite attempts at performance tweaks this would never finish executing.

let problem41a = 
    let isPandigital n =
        let dlist = n |> digits |> List.ofSeq
        (List.sort dlist) = [1..List.length dlist]
        
    let rec loop n =
        if isPrime n && isPandigital n then n
        else loop (n-2)
    loop 987654321

Then I realized I would have much better luck generating pandigital numbers and testing them for primality using the lexical permutation algorithm from Problem 24.  The following is a generic implementation with a immutable sequence wrapper.

First we need a couple operators: comparer converts an F# function into an IComparer so we can use the System.Array.Sort overload which allows in-place sub range sorting.  flip reverses the parameters of two parameter functions.

let comparer f = { new System.Collections.Generic.IComparer<'a> with member self.Compare(x,y) = f x y }

let flip f x y = f y x

Next is our permutations function which is generic and takes a comparison function.  The inner permute function mutates the given perm array returning false when the array is at its last permutation.  Then a sequence expression is used to generate a sequence with immutable copies of the array after each permutation.  Finally, permutationsAsc and permutationsDesc are convenience partial applications of permutations.  Despite the fact that the array is copied for each yield of the sequence, this performs quite well.

let permutations f e =
    ///Advances (mutating) perm to the next lexical permutation.
    let permute (perm:'a[]) (f: 'a->'a->int) (comparer:System.Collections.Generic.IComparer<'a>) : bool =
        try
            //Find the longest "tail" that is ordered in decreasing order ((s+1)..perm.Length-1).
            //will throw an index out of bounds exception if perm is the last permuation,
            //but will not corrupt perm.
            let rec find i =
                if (f perm.[i] perm.[i-1]) >= 0 then i-1
                else find (i-1)
            let s = find (perm.Length-1)
            let s' = perm.[s]
            
            //Change the number just before the tail (s') to the smallest number bigger than it in the tail (perm.[t]).
            let rec find i imin =
                if i = perm.Length then imin
                elif (f perm.[i] s') > 0 && (f perm.[i] perm.[imin]) < 0 then find (i+1) i
                else find (i+1) imin
            let t = find (s+1) (s+1)
                
            perm.[s] <- perm.[t]
            perm.[t] <- s'

            //Sort the tail in increasing order.
            System.Array.Sort(perm, s+1, perm.Length - s - 1, comparer)
            true
        with
        | _ -> false
       
    //permuation sequence expression 
    let c = f |> comparer
    let freeze arr = arr |> Array.copy |> Seq.readonly
    seq { let e' = Seq.toArray e
          yield freeze e'
          while permute e' f c do
              yield freeze e' }
              
let permutationsAsc e = permutations compare e
let permutationsDesc e = permutations (flip compare) e

Now we have the solution to our problem.

let problem41c =    
    let rec loop n =
        let maybe = 
            {n..(-1)..1}
            |> permutationsDesc
            |> Seq.map Digits.toInt
            |> Seq.tryFind isPrime
            
        match maybe with
        | Some(value) -> value
        | None -> loop (n-1)
        
    loop 9

Note: apparently if the sum of the digits of a number is divisible by 3 then the number cannot be prime.  This isn’t obvious to me, but it’s late so I’ll look into to it more tomorrow.  However, if we take this fact we find that the number of digits must then either be 4 or 7.  Applying the 7 digit upper bound, both solution (a) and (b) run instantaneously.