Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 38: Pandigital multiples

Problem 38

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?

Solution

This problem can be brute-forced quite easily, but lets do some analysis to shrink the search space. We need to find a 9-digit pandigital number greater than the given 918273645, which implies that the first digit of the concatenated number starts with 9 as well. Since \(n > 1\), the trivial solution of \(987654321\cdot 1\) is not allowed and with \(n\) being at least two, the maximum digit count of the fixed number \(x\) is forced to be \(\leq 4\).

If the fixed number \(x\) is a two-digit number, all resulting numbers will have \(<9\) digits with \(n\leq 3\) and \(>9\) with \(n\geq 4\), which allows us to exclude the range \(90\leq x < 100\). If the fixed number \(x\) is a three-digit number, all resulting numbers will be \(\neq 9\) as well, which excludes the range \(900\leq x<1000\). Finally, if \(x\) is a four-digit number, we will get a 9 digit number, which leaves us with the first rough valid range of \(9000\leq x < 10000\). This interval can be reduced to valid pandigital values, which results in an interval of \(9123\leq x \leq 9876\). If we check again the length argument, we can lift the lower bound to 9213, since 9123 will not result in a 9 digit number, which gives the new interval \(9213\leq x \leq 9876\).

When digging a little deeper, we see that if the second digit is \(>4\), a carry over happens and two 9s are produced in the solution. A similar observation shows that non of the digits can be 1 since we will otherwise end up with two 1s in the solution. This allows us to further reduce the search space to \(9234\leq x\leq 9487\).

Multiplied by two, the interval is \(18468 \leq x\leq 18974\), which says that concatenating \(x\) and \(2x\) can be done with \(100000x + 2x\) or better \(100002x\). When we use the isPandigital function of Problem 32, the solution is just

function solution() {
  for (let x = 9487; x >= 9234; x--) {
  let res = 100002 * x;
    if (isPandigital(res)) {
      return res;
    }
  }
  return null;
}

« Back to problem overview