Project Euler Solution #92: Square digit chains

Problem 92

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Solution

The largest possible sum of squares is created by the number \(9999999\), which is \(7\cdot 9^2 = 567\). We can use this number as our cache size since all other numbers below 10 million are just permutations with a smaller a smaller sum of their squared digits:

function endsWith89(n) {
  do {
    let s = 0;
    while (n) {
      let x = n % 10;
      s+= x * x;
      n = n / 10 | 0;
    }
    n = s;
  } while (n !== 1 && n !== 89);
  return n === 89;
}

let cache = [false];
for (let i = 1; i <= 567; i++) {
  cache.push(endsWith89(i));
}

When we now see the number \(abcdefg\) with \(a\leq b\leq c\leq d\leq e\leq f\leq g\), we check the digits against our cache. If the chain ends in 89, we need to add all possible combinations to the result, which ends in the multinomial coefficient \(\frac{7!}{C_0!\cdot C_1!\cdot\ldots\cdot C_9!}\) due to the set constraint - where \(C_1\) is the number of 1's, \(C_2\) the number of 2's and so on.

function solution() {
  let res = 0;

  let factorials = [1, 1, 2, 6, 24, 120, 720, 5040];

  for (let g = 0; g <= 9; g++)
  for (let f = 0; f <= g; f++)
  for (let e = 0; e <= f; e++)
  for (let d = 0; d <= e; d++)
  for (let c = 0; c <= d; c++)
  for (let b = 0; b <= c; b++)
  for (let a = 0; a <= b; a++) {

    let cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let dig = [a, b, c, d, e, f, g];
    let sum = 0;

    for (let di of dig) {
      sum+= di * di;
      cnt[di]++;
    }

    if (cache[sum]) {
      let den = 1;
      for (let ci of cnt) {
        den*= factorials[ci];
      }
      res+= factorials[7] / den;
    }
  }
  return res;
}

We solve the problem now in \({9 + 7\choose 9}=11440\) (times the inner loops) iterations, instead of working on 10M numbers.