C++で実装する拡張ミディの定理（Extended Midy's Theorem）

拡張ミディの定理とは

ミディの定理（Midy's Theorem）は、分数 n/p の小数展開に関する定理です。ここで n は任意の整数、p は素数であり、n/p が偶数桁の循環小数になるとき、循環節を半分に分割してその2つの数を足し合わせると、必ず 999…9（すべて9が並んだ数）になります。

この考え方を一般化したものが拡張ミディの定理（Extended Midy's Theorem）です。循環節を m 桁ずつのブロックに分割したとき、それらの総和は 10^m − 1 の倍数になる、というものです。

例えば 1/17 = 0.0588235294117647 の場合、循環節「0588235294117647」を4桁ずつに区切ると「0588」「2352」「9411」「7647」となり、その和は 19998 = 2 × 9999 となり、9999（= 10⁴ − 1）の倍数であることが確認できます。

C++による実装例

以下のプログラムでは、まず分数の小数展開を計算して循環節を求め、その後、分母が素数かどうかの判定と循環節の長さのチェックを行い、拡張ミディの定理が成り立つかどうかを検証します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

// 分母 den に対する分子 num の小数展開から循環節を求める
string findDecimalValue(int num, int den) {
    string res;
    unordered_map<int, int> mp; // 余りと出現位置を記録
    int rem = num % den;

    while ((rem != 0) && (mp.find(rem) == mp.end())) {
        mp[rem] = res.length();
        rem = rem * 10;
        int part = rem / den;
        res += to_string(part);
        rem = rem % den;
    }
    return (rem == 0) ? "-1" : res.substr(mp[rem]);
}

// 素数判定
bool isPrime(int n) {
    for (int i = 2; i <= n / 2; i++)
        if (n % i == 0)
            return false;
    return true;
}

// 拡張ミディの定理の検証
void ExtendedMidysAlgo(string str, int n, int m) {
    if (!isPrime(n)) {
        cout << "Denominator is not prime, thus Extended Midy's theorem is not applicable";
        return;
    }

    int l = str.length();
    if (l % 2 == 0 && l % m == 0) {
        int part[m] = { 0 }, sum = 0, res = 0;
        // 循環節を m 桁ずつに分割
        for (int i = 0; i < l; i++) {
            int var = i / m;
            part[var] = part[var] * 10 + (str[i] - '0');
        }
        // 各ブロックの表示と総和の計算
        for (int i = 0; i < m; i++) {
            sum = sum + part[i];
            cout << part[i] << " ";
        }
        cout << endl;
        res = pow(10, m) - 1;
        if (sum % res == 0)
            cout << "Extended Midy's theorem holds!";
        else
            cout << "Extended Midy's theorem doesn't hold!";
    }
    else if (l % 2 != 0) {
        cout << "The repeating decimal is of odd length thus Extended Midy's theorem is not applicable";
    }
    else if (l % m != 0) {
        cout << " The repeating decimal can not be divided into m digits";
    }
}

// ドライバーコード
int main()
{
    int numr = 1, denr = 17, m = 4;
    string res = findDecimalValue(numr, denr);
    if (res == "-1")
        cout << "The fraction does not have repeating decimal";
    else {
        cout << "Repeating decimal = " << res << endl;
        ExtendedMidysAlgo(res, denr, m);
    }
    return 0;
}

出力結果

Repeating decimal = 0588235294117647
588 2352 9411 7647
Extended Midy's theorem holds!

プログラムの解説

このプログラムは、主に3つの関数で構成されています。

• findDecimalValue関数： 長除法（筆算の割り算）の要領で小数展開を計算します。余りをハッシュマップに記録することで、同じ余りが再び現れた位置以降を循環節として抽出します。余りが0になった場合は循環しないため「-1」を返します。
• isPrime関数： 2から n/2 まで順に割り切れるかを調べるシンプルな素数判定です。拡張ミディの定理は分母が素数であることが前提となるため、事前チェックに使われます。
• ExtendedMidysAlgo関数： 循環節の文字列を受け取り、m 桁ずつに分割して各ブロックの数値の総和を求めます。総和が 10^m − 1 で割り切れれば「定理が成立」、そうでなければ「不成立」と出力します。また、循環節の長さが奇数の場合や m で割り切れない場合には、定理が適用できない旨を通知します。

実行例では 1/17 を扱っており、循環節「0588235294117647」（16桁）を4桁ずつ4つのブロックに分割すると、その和が 9999 の倍数になることが確認できました。

まとめ

拡張ミディの定理は、循環小数の美しい性質を示す興味深い定理です。本記事のC++プログラムのように、小数展開の計算・素数判定・ブロック分割による検証を組み合わせることで、実際に定理が成り立つことを簡単に確認できます。他の素数（例：7、13、19など）や異なる m の値でも試してみると、定理の挙動をより深く理解できるでしょう。