Project Euler Solution #62: Cubic permutations

Problem 62

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution

With the hint of permutation, the authors of the problem lay a false trail. The easiest way to tackle the problem is to generate cubic numbers \(1^3, 2^3, 3^3, \dots\) until the number of unique digit occurrences reaches five.

As a unique digit representation for a cubic number, we could use a hash or simply a number with sorted digits, like e.g. \(12^3=1728\), where the unique representation would be \(8721\). Sorting the digits of a number \(n\) can be done in \(O(\log n)\) using Counting-sort by creating 10 buckets for counting the digits and concatenating the digits in the right order afterwards:

function sortDigits(n) {

  const buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  let ret = 0;
  while (n > 0) {
      buckets[n % 10]++;
      n = Math.floor(n / 10);
  }

  for (let v = 9; v >= 0; v--) {
      ret = (10 ** buckets[v] * (v + 9 * ret) - v) / 9;
  }
  return ret;
}

It is important to sort the digits in descending order to not cut off zeros at the beginning. But how does the concatination step work? For each iteration, we want to append a number with \(b_i\) (stored as buckets[i]) digits and digit value \(v_i\). To generate such a number, we need to multiply the number \(1111...\) with \(v_i\), that is

\[v_i\sum\limits_{k=0}^{b_i-1}10^k = \frac{v_i}{9}(10^{b_i}-1)\]

When we now create space for \(b_i\) digits on the resulting number \(r_i\) by shifting it with a power of 10, we can formulate the recurrence relationship

\[\begin{array}{rl} r_i &= r_{i-1} \cdot 10^{b_i} + \frac{v_i}{9} \cdot (10^{b_i} - 1)\\ &= \frac{1}{9}(10^{b_i}\cdot(v_i + 9 r_{i-1}) - v_{i}) \end{array}\]

To solve the problem, we create a key-value store to count the occurrences of the permutations. Since we need to find the smallest cube of a family, we also save the first index of a number with a certain digit set in the same place. This works since we walk from bottom up.

function solution(len) {
  const cubes = new Map;

  for (let n = 1; ; n++) {
      let key = sortDigits(n * n * n);
      let cube = cubes.get(key);

      if (cube === undefined) {
          cube = { smallest: n, count: 1 };
          cubes.set(key, cube);
      } else if (++cube.count === len) {
          return cube.smallest ** 3;
      }
  }
}

This algorithm works perfectly fine, but actually we only formulated an insufficient algorithm so far, that incidentally gives the right answer. It still could happen that the number we found has more than 5 permutations. But what is the maximum number we can get from a permutation? sortDigits(n), which is stored as key in the last round before we terminate the function! This is a second benefit that we sorted the number in descending order! So we implement an upper bound check as soon as we find a candidate and for each candidate we check if we reach the bound without changing the count:

function solution(len) {
  const cubes = new Map;
  const candidates = [];
  for (let n = 1; ; n++) {
      let key = sortDigits(n * n * n);
      let cube = cubes.get(key);

      if (cube === undefined) {
          cube = { smallest: n, count: 1 };
          cubes.set(key, cube);
      } else if (++cube.count === len) {
          // Duck type upper bound attribute
          cube.bound = Math.floor(key ** (1 / 3));
          candidates.push(cube);
      }

      for (let i = 0; i < candidates.length; i++) {
          const c = candidates[i];
          if (c.bound >= n && c.count === len) {
              return c.smallest ** 3;
          }
      }
  }
}

This way we know for certain that the first series of cube roots with the stated condition is \(5027, 7061, 7202, 8288, 8384\) and the second series is \(5196, 8124, 8496, 9702, 9783\).