Project Euler — Problem 43 Solution

Problem

The num­ber, 1406357289, is a 0 to 9 pandig­i­tal num­ber because it is made up of each of the dig­its 0 to 9 in some order, but it also has a rather inter­est­ing sub-string divis­i­bil­i­ty prop­er­ty.

Let d1 be the 1st dig­it, d2 be the 2nd dig­it, and so on. In this way, we note the fol­low­ing:

  • d2d3d4=406 is divis­i­ble by 2
  • d3d4d5=063 is divis­i­ble by 3
  • d4d5d6=635 is divis­i­ble by 5
  • d5d6d7=357 is divis­i­ble by 7
  • d6d7d8=572 is divis­i­ble by 11
  • d7d8d9=728 is divis­i­ble by 13
  • d8d9d10=289 is divis­i­ble by 17

Find the sum of all 0 to 9 pandig­i­tal num­bers with this prop­er­ty.

Solution

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)

// generate the 0 to 9 pandigitals
let numbers = permute [0..9] |> List.map (fun l -> l |> List.map string |> List.reduce (+))

// the corresponding prime divisors and digits
let primes = [2; 3; 5; 7; 11; 13; 17]
let ns = [2..10] |> Seq.windowed 3 |> Seq.toList

// returns the number retrieved from taking the digits at the supplied positions
let d ns (numberStr:string) = 
    int(ns |> Array.map (fun n -> numberStr.[n-1].ToString()) |> Array.reduce (+))

// predicate which identifies pandigital numbers with the desired property
let predicate number = List.forall2 (fun n p -> (d n number) % p = 0) ns primes

let answer = numbers |> List.filter predicate |> List.sumBy int64

One thing you might notice in the cre­ation of the per­mu­ta­tions of all 0 to 9 pandig­i­tal num­bers is the use of (+) in the List.reduce func­tion call. This is actu­al­ly just the short­ened form of:

List.reduce (fun acc item –> acc + item)

Anoth­er List func­tion of inter­est here is the List.forAll2 func­tion, which tests if all cor­re­spond­ing ele­ments in both lists sat­is­fy the giv­en pred­i­cate pair­wise. In this case, I’m using it to pair up the dig­its list ([[2;3;4]; [3;4;5];…]) with the primes list ([2;3;5;..17]) to test if a giv­en num­ber has the desired prop­er­ty as described in the prob­lem brief.

We arrive at the answer by sim­ply adding up all the pandig­i­tal num­bers which match­es the pred­i­cate con­di­tion.