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.

## No comments:

## Post a Comment