Bruteforce with Memoization to Count the Square Digit Chains
- 时间:2020-09-09 14:04:20
- 分类:网络文摘
- 阅读:98 次
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 → 89Therefore 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) —
推荐阅读:子鱼论战原文及翻译 阴饴甥对秦伯原文及翻译 诗词名句鉴赏:青青子衿,悠悠我心。 敬姜论劳逸原文及翻译 存在不足,努力改进 神女峰作文 充实温馨的端午节作文600字 最最温柔的力量… 我和差不多的关系作文750字 写人作文夸夸我们班作文400字
- 评论列表
-
- 添加评论