なんかコラッツ予想に立ち向かうやつ！！（パワー系備忘録）〜Dev.Note vol.1
初めに…
これは単純なプログラムを使って頭筋で計算（未解決）するものです。数学の難しい定理などは知りません。あと、筆者の環境はゴミなので環境いい人代わりにやって。あと、改良とか結果とかあったら教えてください！
コラッツ予想とは？
まず、そもそもコラッツ予想とはなんやと思った人のために説明する。数学者たちを悩ませてるなんかすごい問題。簡単に説明すると、好きな数を取って、偶数なら2で割る。奇数なら3倍して1を足す。それを1になるまで繰り返すってルール。
仕組みはめっちゃシンプル！例えば10って数があったら、「10 ÷ 2 = 5」「3×5 + 1 = 16」「16 ÷ 2 = 8...」って感じで繰り返して最終的に1になるまで計算し続ける。ただこれ、どの数でも必ず1になるのかって？それは現在に至るまで誰も証明できてない。
なんでこんなに頭痛くなるのか？
これがただの暇つぶしじゃ終わらない。なぜかというと、数によってはめっちゃ跳ね上がる。例えば、27から始めると数が爆発して上がったり下がったりでめっちゃ時間かかる！でも、なんだかんだで1にはなるってのが面白いところ。でも、どの数でも絶対1になるかどうかは、誰も証明できてないってのがこの問題のなんかいいところ！
プログラムの概要
でも、四則演算しかでてきてないし、ワンチャン簡単な計算ならプログラミングで解けるかも！やってみるか！こっからは、少し真面目モードで。はたしていけるかどうか。
プラットフォーム: Google Colab（導入についてはめんどくさいので割愛）
あと、競技プログラミングもそうだけど、c++などのインタープリター言語がやっぱり処理速度速いらしい。だからそれ使おう！
言語: C++（Boostライブラリを使用してる。）
作るプログラムは、もちろんコラッツ予想に関連する数値計算を行うもの。具体的には、始めの数値と終わりの数値を指定して、その範囲内の整数について、各数がコラッツ予想の過程で1に到達するまでのステップ数を計算し、以下の情報を出力する感じ。
最大ステップ数を持つ数値: 指定範囲内で最も多くのステップを要した数値。
最大ステップ数: その数値が1に到達するまでにかかったステップ数。
実行時間: 計算にかかった総時間。
特徴としては・・・
多倍長整数の使用: Boost.Multiprecisionライブラリのcpp_int型を使用し、非常に大きな数値まで扱えるようにする。
並列処理の実装: OpenMPを使用して、計算をマルチスレッドで並列化してる。
メモ化による最適化: 計算済みの数値とそのステップ数をメモ化し、重複計算を避けています。ただ、メモの数が大きいと同期処理によるオーバーヘッドが起こるかも・・・
進行状況の表示: 計算の進捗率をリアルタイムで表示し、長時間の計算でも進行状況を把握できるようにしてる。
実行の流れ
ライブラリのインストール
Boostライブラリはデフォルトでインストールされていないため、apt-getコマンドでインストールが必要。あと、インストールに時間がかかるかもしらん。（ライブラリのダウンロードとインストールには数分かかる場合があります。）
!apt-get update
!apt-get install -y libboost-all-devメインコードについて
重要な点（めんどくさい人は飛ばしてOK）
Google ColabでのC++実行
マジックコマンドの使用: %%writefileを使用してC++コードをファイルに書き込み。
セルの先頭に記述: マジックコマンドはセルの最初の行に記述し、空行を入れないように。
Boostライブラリのインストール
必要なパッケージのインストール: さきほどもお伝えした通り、Boostライブラリはデフォルトでインストールされていないので、apt-getコマンドでインストールが必要。
コンパイルエラーの対処
std::atomicの使用: std::atomicはトリビアルにコピー可能な型にのみ使用可能らしい。cpp_int型は非対応だったので、進行状況のカウンタにはunsigned long long型を使用しました。
入力時の注意
半角数字の使用: プログラムへの入力は絶対半角数字！ 全角数字を入力すると、プログラムが正しく認識できないのか、無限ループになる。
大きな数値の入力: すごく大きな数値を入力する場合、計算時間とメモリ使用量がめっちゃ増える。Google Colabでやるなら制限内で実行可能な範囲を指定して。
進行状況の表示
std::atomicと型の制限: 進行状況を表示するためにstd::atomic<unsigned long long>を使用しているが、unsigned long longの最大値を超える範囲は正しく進捗が表示できない場合がある。
進捗表示の頻度: 進捗の更新は全体の1%ごとに表示するようにした。これでわかりやすいぜ！
並列処理の実装
OpenMPの使用: #pragma omp parallelディレクティブを使って、複数のスレッドで計算を並列化してる。
スレッド間の競合防止: #pragma omp criticalを使用して、共有データへのアクセスを保護してる。
メモリ使用量の管理
メモ化の効果と影響: メモ化により一度計算した値を覚えておける、でも、メモリ使用量が増加しちゃう。だから、範囲が大きい場合、メモリ不足になる可能性がある（課題）。
スレッドローカルなメモ化: スレッドごとに独自のメモリ空間を使用することで、データ競合を防いでる。
実行時間の計測
<chrono>ライブラリの使用: プログラムの開始から終了までの時間を測って、ミリ秒単位で表示してる。
パフォーマンスの最適化: コンパイル時の最適化オプション（-O3、-fopenmp）を使用して、実行速度を向上させてるつもり。
ソースコードはこれ！！！！
%%writefile collatz.cpp /／GoogleColabで動作をさせるため、これはc++だよと教えるとこ。
#include <iostream>
#include <omp.h>
#include <vector>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>
#include <chrono>
#include <atomic>
// Boost.Multiprecisionの名前空間
using namespace boost::multiprecision;
using namespace std::chrono;
// 多倍長整数型を定義
typedef cpp_int BigInt;
// コラッツ予想のステップ数を計算する関数（メモ化付き）
unsigned long long collatz(BigInt n, std::unordered_map<BigInt, unsigned long long>& memo) {
unsigned long long steps = 0;
BigInt original_n = n;
std::vector<BigInt> sequence;
// メモ化されている場合はその値を返す
while (true) {
if (n == 1) {
steps += 0;
break;
}
// スレッドローカルのメモに結果があればそれを使用
if (memo.find(n) != memo.end()) {
steps += memo[n];
break;
}
sequence.push_back(n);
// ビット演算を使用して効率化
if ((n & 1) == 0) {
n >>= 1; // nを2で割る
steps++;
} else {
n = 3 * n + 1;
steps++;
}
}
// 計算結果をメモに保存
for (auto it = sequence.begin(); it != sequence.end(); ++it) {
memo[*it] = steps--;
}
return memo[original_n];
}
int main() {
BigInt start_bigint, end_bigint;
// ユーザーからの入力を受け取る
std::cout << "開始番号を入力してください: ";
std::cin >> start_bigint;
std::cout << "終了番号を入力してください: ";
std::cin >> end_bigint;
// 開始番号と終了番号の検証
if (end_bigint < start_bigint) {
std::cerr << "エラー: 終了番号は開始番号以上である必要があります！" << std::endl;
return 1;
}
// 総計算数を計算
BigInt total_numbers_bigint = end_bigint - start_bigint + 1;
// total_numbersをunsigned long longに変換
unsigned long long total_numbers;
try {
total_numbers = total_numbers_bigint.convert_to<unsigned long long>();
} catch (...) {
std::cerr << "エラー: 範囲が大きすぎて進捗表示ができません！" << std::endl;
total_numbers = 0;
}
// スレッド数を取得
int num_threads = omp_get_max_threads();
// 範囲をスレッド数に応じて分割
std::vector<std::pair<BigInt, BigInt>> ranges;
BigInt total = end_bigint - start_bigint + 1;
BigInt chunk_size = total / num_threads;
BigInt remainder = total % num_threads;
BigInt current_start = start_bigint;
for (int i = 0; i < num_threads; ++i) {
BigInt current_end = current_start + chunk_size - 1;
if (i < remainder) {
current_end += 1;
}
ranges.push_back(std::make_pair(current_start, current_end));
current_start = current_end + 1;
}
// 計測開始
auto start_time = high_resolution_clock::now();
// 最大ステップ数と対応する数値を記録
unsigned long long max_steps = 0;
BigInt number_with_max_steps = 0;
// 進行状況をカウントする変数
std::atomic<unsigned long long> progress_count(0);
// 進捗表示のタイミングを設定（全体の1%ごとに表示）
unsigned long long progress_step = total_numbers / 100;
if (progress_step == 0) progress_step = 1;
// OpenMPによる並列処理
#pragma omp parallel
{
// スレッド番号を取得
int thread_num = omp_get_thread_num();
BigInt local_start = ranges[thread_num].first;
BigInt local_end = ranges[thread_num].second;
// スレッドローカルなメモ化用ハッシュマップ
std::unordered_map<BigInt, unsigned long long> memo;
unsigned long long local_max_steps = 0;
BigInt local_number_with_max_steps = 0;
BigInt n = local_start;
while (n <= local_end) {
unsigned long long steps = collatz(n, memo); // コラッツ予想のステップ数を計算
if (steps > local_max_steps) {
local_max_steps = steps;
local_number_with_max_steps = n;
}
// 進行状況の更新
if (total_numbers > 0) {
unsigned long long current_progress = ++progress_count;
// 進捗の表示
if (current_progress % progress_step == 0 || current_progress == total_numbers) {
double percentage = (current_progress * 100.0) / total_numbers;
#pragma omp critical
{
std::cout << "進行状況: " << percentage << "% 完了" << std::endl;
}
}
}
++n;
}
// 最大ステップ数を更新
#pragma omp critical
{
if (local_max_steps > max_steps) {
max_steps = local_max_steps;
number_with_max_steps = local_number_with_max_steps;
}
}
}
// 計測終了
auto end_time = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(end_time - start_time);
// 最大ステップ数とその数値を表示
std::cout << "最大ステップ数を持つ数値はこれ！: " << number_with_max_steps << std::endl;
std::cout << "最大ステップ数: " << max_steps << std::endl;
// 実行時間を表示
std::cout << "実行時間: " << duration.count() << "ミリ秒" << std::endl;
return 0;
}
コンパイルをして・・・
!g++ -O3 -fopenmp -o collatz collatz.cpp実行方法はこれ
!./collatz実行！ちょっと長いよ。
開始番号を入力してください: 1
終了番号を入力してください: 100000
進行状況: 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% 完了
進行状況: 27% 完了
進行状況: 28% 完了
進行状況: 29% 完了
進行状況: 30% 完了
進行状況: 31% 完了
進行状況: 32% 完了
進行状況: 33% 完了
進行状況: 34% 完了
進行状況: 35% 完了
進行状況: 36% 完了
進行状況: 37% 完了
進行状況: 38% 完了
進行状況: 39% 完了
進行状況: 40% 完了
進行状況: 41% 完了
進行状況: 42% 完了
進行状況: 43% 完了
進行状況: 44% 完了
進行状況: 45% 完了
進行状況: 46% 完了
進行状況: 47% 完了
進行状況: 48% 完了
進行状況: 49% 完了
進行状況: 50% 完了
進行状況: 51% 完了
進行状況: 52% 完了
進行状況: 53% 完了
進行状況: 54% 完了
進行状況: 55% 完了
進行状況: 56% 完了
進行状況: 57% 完了
進行状況: 58% 完了
進行状況: 59% 完了
進行状況: 60% 完了
進行状況: 61% 完了
進行状況: 62% 完了
進行状況: 63% 完了
進行状況: 64% 完了
進行状況: 65% 完了
進行状況: 66% 完了
進行状況: 67% 完了
進行状況: 68% 完了
進行状況: 69% 完了
進行状況: 70% 完了
進行状況: 71% 完了
進行状況: 72% 完了
進行状況: 73% 完了
進行状況: 74% 完了
進行状況: 75% 完了
進行状況: 76% 完了
進行状況: 77% 完了
進行状況: 78% 完了
進行状況: 79% 完了
進行状況: 80% 完了
進行状況: 81% 完了
進行状況: 82% 完了
進行状況: 83% 完了
進行状況: 84% 完了
進行状況: 85% 完了
進行状況: 86% 完了
進行状況: 87% 完了
進行状況: 88% 完了
進行状況: 89% 完了
進行状況: 90% 完了
進行状況: 91% 完了
進行状況: 92% 完了
進行状況: 93% 完了
進行状況: 94% 完了
進行状況: 95% 完了
進行状況: 96% 完了
進行状況: 97% 完了
進行状況: 98% 完了
進行状況: 99% 完了
進行状況: 100% 完了
最大ステップ数を持つ数値: 77031
最大ステップ数: 350
実行時間: 604ミリ秒おわり！とりあえず１０００００まで測ってみた。604ミリ秒。体感pythonの十分の一ぐらいの速さで出た気がする。
ここからが本番だ！！！！
100000まで終わった。よし、ウォーミングアップは終了して、次は２の６４乗ー１まで計算してみるか！「2^64 - 1」は18,446,744,073,709,551,615 。この数は、64ビットの符号なし整数型（unsigned long long）で表現できる最大値のひとつ。ここまで計算すれば、解決できるのでは...？いざ勝負！！
おおおおおおおおおおおおおお
おおおおおおおおおおおぉぉぉぉぉぉぉぉぉぉぉ
ぉぉぉぉぉぉぉぉぉぉぉ…………………………………..ながい！！！！
永遠に終わらない。どれだけ待っても１パーセントも終わらない……
たしか１０万まで計算するのにかかった時間は６０４ミリ秒だろ？
てことは、18,446,744,073,709,551,615（2^64-1）を１０万で割って大体1.845^e14だろ (184470000000000) 。それを0.603秒(603ミリ秒）で掛けるから……10^14秒か……????
GPT「10^14秒は約 1,157,407,407日、つまり約 3,168,808年 に相当します。これほどの時間は非常に長く、数百万年のスケールになりますね。」
いや詰んだやん。
おわりに…
何の成果も得られませんでした！！！！
いや、本当に振り返ってみると、確かに無謀な挑戦だったなって、今になって実感してるんだよね。初心者が軽く「これいけるんじゃね？」みたいなノリで突っ込んで解けるような問題なら、とっくに解決してたんだろうなって。でも、それに気づいた時にはもう遅かったわけで……。
でも、コラッツ予想みたいに簡単なはずの問題に、こんなに深い謎が詰まってるなんて思わなかった。シンプルな数の操作が、なんでこんなに難しいのか？数学っていうは本当に奥が深い気がする。自分の悩みなんてほんとにちっぽけだなって感じた瞬間だった。数学ってすごい。
だから、これを読んでる皆さんに言いたい。まだ解けてないからこそ、価値があると。もしかしたら、あなたが解決するかもしれないし、もっとすごいアイデアが浮かぶかもしれない。そうなったら、ぜひ俺に教えてほしい！この未解決の謎を、君がついに解いたって瞬間、見逃したくないからさ。
