Project Euler — Problem 32 Solution

Problem

We shall say that an n-dig­it num­ber is pandig­i­tal if it makes use of all the dig­its 1 to n exact­ly once; for exam­ple, the 5-dig­it num­ber, 15234, is 1 through 5 pandig­i­tal.

The prod­uct 7254 is unusu­al, as the iden­ti­ty, 39 x 186 = 7254, con­tain­ing mul­ti­pli­cand, mul­ti­pli­er, and prod­uct is 1 through 9 pandig­i­tal.

Find the sum of all prod­ucts whose multiplicand/multiplier/product iden­ti­ty can be writ­ten as a 1 through 9 pandig­i­tal.

HINT: Some prod­ucts can be obtained in more than one way so be sure to only include it once in your sum.

Solution

let isPandigital(n) =
    let upperBound = int32(sqrt(double(n)))

    [2..upperBound]
    |> Seq.filter (fun x -> n % x = 0)
    |> Seq.map (fun x -> x.ToString()+(n/x).ToString()+n.ToString())
    |> Seq.exists (fun str -> 
        [1..9]
        |> List.map (fun n -> n.ToString())
        |> List.forall (fun n -> str.Contains(n) && str.IndexOf(n) = str.LastIndexOf(n)))

let answer = [1000..9999] |> List.filter isPandigital |> List.sum

This prob­lem here is some­what open end­ed in terms of how far you have to go before you can be sure that you’ve checked all the rel­e­vant num­bers, i.e. do I have to cov­er all 1–5 dig­its num­bers, or 1–9, or some­where in between?

To answer that, think of each of mul­ti­pli­cand, mul­ti­pli­er and prod­uct as a * (10 POW b) – e.g. 39 = 0.39 * (10 POW 2), 186 = 0.186 * (10 POW 3) and 7254 = 0.7254 * (10 POW 4) – then you end up with:

a1 * (10 POW b1) * a2 * (10 POW b2) = a3 * (10 POW b3) where b1 + b2 + b3 = 9 and b1 + b2 >= b3

As it turns out the only b3 which sat­is­fies both cri­te­ria is 4, so we only need to check 4-dig­it prod­ucts, hence you see in my solu­tion that I’ve only con­sid­ered the num­bers from 1000 to 9999.