Project Euler Solution #38: Pandigital multiples

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;
}