Computing the Longest Recurring Cycle in its Decimal Fraction Pa
- 时间:2020-09-10 12:45:51
- 分类:网络文摘
- 阅读:102 次
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
Computing the Longest Recurring Cycle using Hash Map
By repeatedly doing the division, we multiple by ten the quotient. If the quotient has appeared previously, we know that we have a recurring cycle. The first time the quotient appears, we remember the position, and the second time when same quotient occurs, we compute the position offset, which is the length of the recurring cycle.
We can use a hash map (or dictionary) to remember the position of the recurring cycle – key value pair where key is the quotient and value is the position when this quotient appears.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | function reciprocal(d) { let hash = {}; let x = 1, i = 0; while (x != 0) { i ++; x *= 10; let y = Math.floor(x / d); if (typeof hash[x] === 'undefined') { hash[x] = i; } else { return i - hash[x]; } x = x % d; } return 0; } let ans = 1, v = 0; for (let d = 1; d < 1000; d ++) { const r = reciprocal(d); if (r >= v) { v = r; ans = d; } } console.log(ans); |
function reciprocal(d) { let hash = {}; let x = 1, i = 0; while (x != 0) { i ++; x *= 10; let y = Math.floor(x / d); if (typeof hash[x] === 'undefined') { hash[x] = i; } else { return i - hash[x]; } x = x % d; } return 0; } let ans = 1, v = 0; for (let d = 1; d < 1000; d ++) { const r = reciprocal(d); if (r >= v) { v = r; ans = d; } } console.log(ans);
The answer is 983 where 1/983 has longest recurring cycle of 982.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:The Importance of SEO and How They Improve the Number of Your Cl Learn The Basics Of Google My Business Iterative and Recursion Algorithms to Compute the Number of Step How to Check if a DLL or EXE is 32-bit or 64-bit (x86 or x64) us C++: How to Iterate the Elements over the Sets (set, unordered_s How to Iterate over the Items in Java’s Map (HashMap, Hash Dynamic Programming Algorithm to Count Vowels Permutation Exploring the Importance of Brand Consistency Cleaning A WordPress Malware Infection For Dummies 7 Killer Ways to Higher Average Time on Page
- 评论列表
-
- 添加评论