Skip to content

Project Euler Problem 32

November 22, 2011

In order to solve Project Euler Problem 32 let’s find how many digits should our multiplicand, multiplier, and product have in order to yield 9 digits overall:

let maxNum digits = pown 10 digits - 1
let minNum digits = pown 10 (digits - 1)
let nDigits num = int (log(float num) / log(10.)) + 1
let splits9into3 =
    [
        for a = 1 to 9 do
            for b = 1 to 9 do
                for c = 1 to 9 do
                    if a + b + c = 9 then
                        yield [a;b;c]
    ]

let isCandidate split =
    let [a;b;c] = split
    nDigits ((maxNum a) * (maxNum b)) > c &&
        nDigits ((minNum a) * (minNum b)) < c

splits9into3 |> List.filter isCandidate |> List.iter (printfn "%A")

After running this snippet it is clear that the sought pieces may look as
d*dddd=dddd and dd*ddd=dddd. Based on this consideration it is easy to brute force the solution:

let isPandigitalProduct (a: int) (b: int) =
    let isPandigitalString (s: string) =
        let ss = s.ToCharArray() |> Set.ofArray
        s.Length = 9 && Set.count ss = 9 && ss.MinimumElement > '0'

    isPandigitalString (sprintf "%d%d%d" a b (a*b))

let problem032 () =
    [
        for i = 2 to 99 do
            for j = i to 9999 do
                if isPandigitalProduct i j then
                    yield (i*j)
    ]
    |> Set.ofList |> Set.toList |> List.sum
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: