The Problem

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192 192 × 2 = 384 192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

The Solution

This is one of those problems where it helps to solve parts of the problem by analysis before proceeding on with a computational solution. I'm a programmer, so every problem I encounter looks like it can be solved with software, and my immediate reaction is usually to start coding and figure out all those pesky details later. It's a reflex I constantly have to suppress.

In order to satisfy the problem definition, all of our answers must be exactly 9 digits long. So, we know two things right off the bat:

• n can't be greater than 9 because that would result in numbers > 9 digits
• The integer being multiplied by the sequence cannot be > 10000, because 10000 concatenated with our smallest sequence (1,2) would yield a number of more than 9 digits.

Knowing these limits, the problem is pretty easy.

Let's start with some helper functions.

let concatProduct i s = 
    let muln x = string(x * i)
    bigint.Parse(System.String.Join("", s |> Seq.map muln))

The concatProduct function takes an integer i and a sequence of other integers s. It multiplies each s by i, converts that to a string, and returns all those strings concatenated.

let digitStrings = [1..9] |> List.map string

let isPandigital n =
    let str = n.ToString()
    if str.Length <> 9 then false
    else
        digitStrings
        |> List.forall (fun x -> str.IndexOf(x) >= 0)

The isPandigital function checks to make sure we have a string exactly 9 characters long and then uses List.forall to make sure each character, 1-9, is in the string.

Now, solving the problem is easy:

let cartesianProduct xs ys = 
    xs 
    |> Seq.collect (fun x -> ys |> Seq.map (fun y -> x, y))

cartesianProduct (seq { 1..9999}) (seq { 2..9 })
|> Seq.map (fun (i,n) -> concatProduct i (seq { 1..n } ))
|> Seq.filter isPandigital
|> Seq.max

We start by generating the cartesian product of seq { 1..100000 } with seq { 2..9 }.

Next, we map each pair to the the concatenatedProduct of i and seq { 1..n }.

Finally, we filter out any product that isn't pandigital and return the maximum, which is the answer to the problem.

Other Posts in This Series