Project Euler Solution #32: Pandigital products

Problem 32

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 × 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.

Solution

Let \(\ell_1, \ell_2\) be the lengths of the factors of the stated problem. We are looking for all numbers whose combined lengths plus the length of their product is 9. The length of the product of two numbers can be calculated using the function \(L\) derived for Problem 25 and can range from length of the smallest \(\ell_1\) and \(\ell_2\) products to the largest. Expressed as interval this means:

\[\begin{array}{rl} & [\ell_1 + \ell_2 + L(10^{\ell_1 - 1} \cdot 10^{\ell_2 - 1}), \ell_1 + \ell_2 + L((10^{\ell_1} - 1) \cdot (10^{\ell_2} - 1))]\\ \Leftrightarrow & [\ell_1 + \ell_2 + L(10^{\ell_1 + \ell_2 - 2}), \ell_1 + \ell_2 + L((10^{\ell_1} - 1)) + L((10^{\ell_2} - 1))]\\ \Leftrightarrow & [2\ell_1 + 2\ell_2 -1, \ell_1 + \ell_2 + 2 + \lfloor\log(10^{\ell_1} - 1))\rfloor + \lfloor\log(10^{\ell_2} - 1))\rfloor]\\ \end{array}\]

Generating some reasonable intervals yields the following table:

It becomes clear that only the highlighted lengths can produce pandigital numbers of the right length. Since multiplication is commutative, we can skip half of the search space and so all we need to do is check if the result is a pandigital number if the first number ranges from 1 to 9 and the second from 1234 to 9876 as well as the first from 12 to 98 and the second from 123 to 987. We could generate all possible pandigital numbers, but as \(_9P_1=9, _9P_2=72, _9P_3=504\) and \(_9P_4=3024\), the search space is still quite big. That means we don't need to write a function to generate all \(k\) permutations \(_nP_k\) out of \(n\) but rather scan over the full range and check if the resulting number is pandigital. To do that we introduce a function to check if a certain number is pandigital:

function isPandigital(n) {

  var m = 0;

  for (var i = 0; n > 0; i++) {
    m|= 1 << n % 10;
    n = n / 10 | 0;
  }
  return 2 + m === 1 << (i + 1);
}

The function cuts off the right most digit in base 10 and uses it as the index of a bit that is set on mask \(m\). For example with \(n=123\) the mask \(m=1110_2\). Adding 1 will fill the least significant bit (LSB) with a 1 and adding another 1 will result in \(10000_2\), which is exactly 1 shifted by the length plus 1. This seamingly excludes zero from being part of a pandigital number and works to check if every digit was present only once for all integers. We can now implement the idea of searching for a pandigital number in a certain range:

var products = new Set;
function sumRange(m0, mn, n0, nn) {
  for (var m = m0; m <= mn; m++) {
    for (var n = n0; n <= nn; n++) {

      var x = m * n;
      var p = Number("" + m + n + x);

      if (isPandigital(p)) {
        products.add(x);
      }
    }
  }
}

By calling the function twice with sumRange(1, 9, 1234, 9876) and sumRange(12, 98, 123, 987), we get all products on the products-set now. Since it's a set, no duplicates are contained and all we need to do is summing over the products finally:

sumRange(1, 9, 1234, 9876);
sumRange(12, 98, 123, 987);
console.log([...products].reduce((a, b) => a + b, 0));