C++でミディの定理を検証する方法

分子を格納する整数 a_num と、素数であることが前提となる分母を格納する整数 p_den が与えられます。この記事では、a_num を p_den で割って得られる循環小数に対する操作により、ミディの定理（Midy's theorem）が成り立つかどうかを検証する方法を解説します。

ミディの定理とは

ミディの定理とは、分母が素数 p である分数 a/p を小数展開したとき、循環節の桁数が偶数であれば、その循環節を前半と後半に分割して加算すると、すべての桁が9になるという定理です。

ミディの定理を証明する手順

• 分子を a_num、分母を p_den（必ず素数）として入力します。

• 割り算を実行し、循環小数を求めます。

• 循環が始まるまでの小数の桁を保存します。

• 循環節の桁数が偶数かどうかを確認し、偶数であれば前後半分に分割します。

• 分割した2つの数を加算します。結果がすべて9の文字列であれば、ミディの定理が証明されます。

以下に入出力のシナリオ例を示します。

入力 − int a_num = 1、int p_den = 19

出力 − 循環小数：052631578947368421　ミディの定理が証明されました

説明 − 上記の手順に従ってミディの定理を確認します。

• 1 ÷ 19 = 0.052631578947368421… となり、循環小数になります。

• 循環節は 052631578947368421（18桁）です。

• 桁を半分に分割します：052631578 と 947368421。

• 両者を加算します：052631578 + 947368421 = 999999999。

• 結果はすべて9の文字列となるため、ミディの定理が証明されました。

入力 − int a_num = 49、int p_den = 7

出力 − 循環小数なし

説明 − 49 は 7 で完全に割り切れるため小数部分が発生せず、循環小数にはなりません。したがって出力は「循環小数なし」となります。

プログラムで使用するアプローチ

• 整数値 int a_num と int p_den を入力します。

• ミディの定理を検証するため、関数 Midys_theorem(a_num, p_den) を呼び出します。

• 関数 check_Midys() 内部の処理：

  • 変数 int first を 0、int last を 0 で初期化します。

  • 関数 check(val) が false を返した場合は「ミディの定理は適用できません」と出力します。

  • len % 2 == 0（桁数が偶数）の場合は、i を 0 から len/2 未満までループし、first を first * 10 + (str[i] - '0')、last を last * 10 + (str[len / 2 + i] - '0') で更新し、「ミディの定理が証明されました」と出力します。

  • それ以外の場合は「ミディの定理は適用できません」と出力します。

• 関数 Midys_theorem(int a_num, int p_den) 内部の処理：

  • int 型をキー・値にもつ map 型変数 map_val を作成し、マップをクリアします。

  • 余り reminder を a_num % p_den に設定します。

  • reminder が 0 でなく、map_val.find(reminder) が map_val.end() と等しい限り、map_val[reminder] に result.length() を設定し、reminder を reminder * 10 に更新、temp を reminder / p_den として result に to_string(temp) を連結し、さらに reminder を reminder % p_den で更新します。

  • 余りが 0 になった場合は "-1" を返し、そうでなければ count に result.substr(map_val[reminder]) を設定します。

  • count を返します。

• 関数 bool check(int val) 内部の処理：

  • i を 2 から val / 2 までループし、val % i == 0 であれば false を返します。ループが完了すれば true を返します（素数判定）。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
bool check(int val){
    for(int i = 2; i <= val / 2; i++){
        if(val % i == 0){
            return false;
        }
    }
    return true;
}
void check_Midys(string str, int val){
    int len = str.length();
    int first = 0;
    int last = 0;

    if(!check(val)){
        cout<<"\nNot applicable for Midy's theorem";
    }
    else if(len % 2 == 0){
        for(int i = 0; i < len / 2; i++){
            first = first * 10 + (str[i] - '0');
            last = last * 10 + (str[len / 2 + i] - '0');
        }
        cout<<"\nProved Midy's theorem";
    }
    else{
        cout<<"\nNot applicable for Midy's theorem";
    }
}
string Midys_theorem(int a_num, int p_den){
    string result;
    map<int, int> map_val;
    map_val.clear();

    int reminder = a_num % p_den;

    while((reminder != 0) && (map_val.find(reminder) == map_val.end())){
        map_val[reminder] = result.length();
        reminder = reminder * 10;
        int temp = reminder / p_den;
        result += to_string(temp);
        reminder = reminder % p_den;
    }
    if(reminder == 0){
        return "-1";
    }
    else{
        string count = result.substr(map_val[reminder]);
        return count;
    }
}
int main(){
    int a_num = 1;
    int p_den = 19;
    string result = Midys_theorem(a_num, p_den);
    if(result == "-1"){
        cout<<"No Repeating Decimal";
    }
    else{
      cout<<"Repeating decimals are: "<<result;
      check_Midys(result, p_den);
   }
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Repeating decimals are: 052631578947368421
Proved Midy's theorem