### 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 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