# Project Euler 92 Solution: 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 → 11
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.

« Back to problem overview