C++でコラッツ予想を実装するプログラムの作成方法

このチュートリアルでは、コラッツ予想(Collatz Conjecture)を実装するC++プログラムについて解説します。

コラッツ予想とは?

コラッツ予想は、1937年にドイツの数学者ロタール・コラッツが提唱した有名な未解決問題です。「任意の正の整数に対して決められた操作を繰り返し適用すると、必ず最終的に1に到達する」という非常にシンプルな主張でありながら、現在まで証明も反証もされていないことで知られています。

本記事では、ある数nが与えられたとき、以下の2つの操作を繰り返し適用することでnを1に変換できるかどうかを判定するプログラムを作成します。

• nが偶数の場合: n を n/2 に置き換える

• nが奇数の場合: n を 3×n + 1 に置き換える

例えば n = 6 の場合、「6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1」という順序で1に到達します。

C++での実装例

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

// nが1に到達するかどうかを再帰的にチェックする関数
bool check1(int n, unordered_set<int> &s){
    if (n == 1)
        return true;
    // すでに訪れた数が再び現れた場合はサイクル(無限ループ)とみなす
    if (s.find(n) != s.end())
        return false;
    s.insert(n);
    return (n % 2) ? check1(3*n + 1, s) :
                     check1(n/2, s);
}

bool if_one(int n){
    unordered_set<int> s;
    return check1(n, s);
}

int main(){
    int n = 234;
    if_one(n) ? cout << "Yes" : cout << "No";
    return 0;
}

出力結果

Yes

コードの解説

• check1()関数: 操作を再帰的に適用しながら、nが最終的に1に到達するかどうかを判定します。nが1になればtrueを返します。

• unordered_set: それまでに現れた数を記録するためのハッシュセットです。同じ数が2回現れた場合、その列は無限ループに陥ると判断できるためfalseを返します。これにより、1に到達できないケースを効率的に検出できます。

• if_one()関数: 訪問済み集合を初期化し、check1()を呼び出すラッパー関数です。

この例では n = 234 を与えています。234は上記の操作を繰り返すことで最終的に1へ到達するため、出力は「Yes」となります。

計算量について

コラッツ予想が正しい限り、このアルゴリズムは必ず停止します。1に到達するまでのステップ数は経験的におおよそO(log n)に比例することが知られており、空間計算量は訪問した数を保存する分だけ必要になります。なお、非常に大きな数を扱う場合は再帰の深さが増えるため、スタックオーバーフローに注意が必要です。必要に応じてwhile文を使った反復処理への書き換えも検討するとよいでしょう。