Computing the Longest Recurring Cycle in its Decimal Fraction Part

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