Computing the Longest Recurring Cycle in its Decimal Fraction Pa

  • 时间:2020-09-10 12:45:51
  • 分类:网络文摘
  • 阅读:106 次

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) —

推荐阅读:
GTV电子体育直播-电子体育在线直播观看「高清」  中天新闻台电视直播台湾中天新闻台简介在线直播  香港卫视新闻综合电视台直播香港卫视在线直播  凤凰卫视香港台直播「高清」  香港卫视直播「高清」  阳光卫视在线直播「高清」  亚洲联合卫视直播「高清」  香港TVB8直播「高清」  卫视体育台直播_星空卫视体育台直播观看「高清」  华娱卫视在线直播「高清」 
评论列表
添加评论