Bruteforce with Memoization to Count the Square Digit Chains

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?

Bruteforce Algorithm to Count eh Sqaure Digit Chains

The easiest thought is to bruteforce, check each number to see if it chains to 89. We can write a chain function to return its final destination:

1
2
3
4
5
6
7
8
9
10
11

function chain(n) {
    while ((n != 1) && (n != 89)) {
        let x = 0;
        while (n > 0) {
            x += (n % 10) * (n % 10);
            n = Math.floor(n / 10);
        }
        n = x;
    }
    return n;
}

function chain(n) {
    while ((n != 1) && (n != 89)) {
        let x = 0;
        while (n > 0) {
            x += (n % 10) * (n % 10);
            n = Math.floor(n / 10);
        }
        n = x;
    }
    return n;
}

While the number is neither 1 or 89 (luckily we don’t need to prove that), we replace the number with the sum of its digits power. Noted in Javascript, you need to truncate the division using e.g. Math.floor.

Then, to do actual bruteforce algorithm:

1
2
3
4
5
6
7
8

let x = 0;
const ten_million = 10000000;
for (let i = 1; i < ten_million; ++ i) {
    if (chain(i) === 89) {
        x ++;
    }
}
console.log(x);

let x = 0;
const ten_million = 10000000;
for (let i = 1; i < ten_million; ++ i) {
    if (chain(i) === 89) {
        x ++;
    }
}
console.log(x);

The answer is 8581146

Bruteforce Algorithm with Memoization to Count the Square Digit Chains

Could we do better? we can optimise the chain function to remember the past outcomes. First we need to rewrite the above chain function using Recursion:

1
2
3
4
5
6
7
8
9
10

function chain(n) {
    if ((n == 1) || (n == 89)) return n;    
    let x = 0;
    while (n > 0) {
        x += (n % 10) * (n % 10);
        n = Math.floor(n / 10);
    }
    // recursive sub-problem
    return chain(x);
}

function chain(n) {
    if ((n == 1) || (n == 89)) return n;    
    let x = 0;
    while (n > 0) {
        x += (n % 10) * (n % 10);
        n = Math.floor(n / 10);
    }
    // recursive sub-problem
    return chain(x);
}

And we can pass a parameter to cache the known results:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function chain(n, cached = {}) {
    if ((n == 1) || (n == 89)) return n;    
    // known results? return it immediately
    if (typeof cached[n] !== 'undefined') {
        return cached[n];
    }
    let x = 0;
    let m = n;
    while (m > 0) {
        x += (m % 10) * (m % 10);
        m = Math.floor(m / 10);
    }
    let ans = chain(x, cached);
    // save it for later lookup
    cached[n] = ans;
    return ans;
}

function chain(n, cached = {}) {
    if ((n == 1) || (n == 89)) return n;    
    // known results? return it immediately
    if (typeof cached[n] !== 'undefined') {
        return cached[n];
    }
    let x = 0;
    let m = n;
    while (m > 0) {
        x += (m % 10) * (m % 10);
        m = Math.floor(m / 10);
    }
    let ans = chain(x, cached);
    // save it for later lookup
    cached[n] = ans;
    return ans;
}

And we then can use this by passing a cache dictionary:

1
2
3
4
5
6
7
8
9

let x = 0;
let cached = {};
const ten_million = 10000000;
for (let i = 1; i < ten_million; ++ i) {
    if (chain(i, cached) === 89) {
        x ++;
    }
}
console.log(x);

let x = 0;
let cached = {};
const ten_million = 10000000;
for (let i = 1; i < ten_million; ++ i) {
    if (chain(i, cached) === 89) {
        x ++;
    }
}
console.log(x);

The performance improvement is around 30 percentage.

–EOF (The Ultimate Computing & Technology Blog) —