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 
评论列表
添加评论