Bruteforce with Memoization to Count the Square Digit Chains
- 时间:2020-09-09 14:04:20
- 分类:网络文摘
- 阅读:107 次
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) —
推荐阅读:食品安全:广州镉超标大米事件追踪 味精的食用安全性及合适用量问题 食品安全问题并不是食品添加剂的错 温州苍南黑作坊两年产千吨剧毒湿米面 食药监总局提醒注意保健食品五大陷阱 对儿童健康成长有益的六大食物 健康养生:七种常见的黑色滋补食物 竹炭食品排毒就是一个忽悠人的概念 中华人民共和国食品安全法(全文) 山东启动打击非法保健食品专项行动
- 评论列表
-
- 添加评论