JavaScriptで1/nの循環小数(循環節)の長さを求める方法

問題

数値 num を第一引数(かつ唯一の引数)として受け取るJavaScript関数を作成します。

この関数には、次の2つの役割があります。

• まず、その数が10と互いに素(共通の約数が1のみ)であるかどうかを判定します。互いに素でない場合は -1 を返します。
• 10と互いに素である場合は、1をその数で割ったときに小数部が循環する桁数(循環節の長さ)を返します。

たとえば、関数への入力が次の場合を考えてみましょう。

入力

const num = 123;

出力

const output = 5;

出力の解説

123は2でも5でも割り切れないため、確実に10と互いに素です。そして1を123で割ると、次のようになります。

1 / 123 = 0.008130081300813…

この結果から、小数部の「00813」が無限に繰り返されていることがわかります。循環している部分の長さは5桁なので、出力は5となります。

サンプルコード

以下が実際のコードです。

const num = 123;
const findRepeatingPart = (num = 1) => {
    if(num % 2 === 0 || num % 5 === 0){
        return -1;
    } else {
        let res = 10 % num, count = 1;
        while(res != 1){

            res = res * 10 % num;
            count++;
        };
        return count;
    }
};
console.log(findRepeatingPart(num));

出力

5

アルゴリズムの仕組み

このアプローチのポイントは剰余演算にあります。10と互いに素な数とは、すなわち2でも5でも割り切れない数のことです。そのため、最初の判定では num % 2 === 0 || num % 5 === 0 で互いに素かどうかを簡単に確認できます。

1/n の割り算を筆算で行うことを思い浮かべると、各ステップで「余りに10を掛けて再度 n で割った余り」を追いかけていることがわかります。小数の循環は、この余りが以前の状態に戻った瞬間に始まります。したがって、余りが再び 1 になるまでループを回し、その反復回数を数えれば、それがそのまま循環節の長さになります。

この方法は筆算のように文字列を扱う必要がなく、純粋な数値計算だけで済むため、非常にシンプルかつ効率的です。