Project Euler – Problem 32 Solution

Problem

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products 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 problem here is somewhat open ended in terms of how far you have to go before you can be sure that you’ve checked all the relevant numbers, i.e. do I have to cover all 1-5 digits numbers, or 1-9, or somewhere in between?

To answer that, think of each of multiplicand, multiplier and product 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 satisfies both criteria is 4, so we only need to check 4-digit products, hence you see in my solution that I’ve only considered the numbers from 1000 to 9999.


Yan Cui

I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.

You can contact me via Email, Twitter and LinkedIn.

Hire me.