コラッツ予想
コラッツ予想とは以下のようなものです。予想ですので、まだ証明はなされていません。
任意の自然数に対して、その数が奇数なら3倍して1を加える。偶数なら2で割る。 この処理を繰り返せば必ず最後には1になる
プログラムはコラッツ予想の定義通りに作っていますが、いくつか工夫した点があります。
まず、計算中に最初の値より下回った場合はそこで終了するようにしています。これは、小さな数字から順に調べていくようにしているため、最初の値以下の数字は既に検証が済んでいるためです。更に言えば、定義より偶数は必ず最初に2で割られて最初の値より下回る事になりますので、奇数のみを調べています。プログラムは3から始めていて2を調べていませんが、2の場合は自明であるという事で省いています。
#include <stdio.h>
#include <gmp.h>
int main( int ac, char *av[] )
{
mpz_t n, n2, start_n, min_n, max_n;
/* コマンドラインから探索範囲を決定する */
if( ac < 3 ) {
printf( "usage : collatz min_n max_n\n" );
return( 1 );
}
mpz_init_set_str( min_n, av[1], 10 );
mpz_fdiv_q_ui(min_n, min_n, 4);
mpz_init_set_str( max_n, av[2], 10 );
mpz_fdiv_q_ui(max_n, max_n, 4);
/* 探索範囲の数を調べる */
mpz_init_set( n, min_n );
mpz_init( n2 );
mpz_init( start_n );
while( mpz_cmp( n, max_n ) <= 0 ) {
mpz_set( n2, n );
mpz_mul_ui( n2, n2, 4 );
mpz_add_ui( n2, n2, 3 );
mpz_set( start_n, n2 );
/* n2がstart_n未満になれば計算終了 */
while( mpz_cmp( n2, start_n ) >= 0 ) {
if( mpz_even_p( n2 ) ) {
/* 偶数なら2で割る */
mpz_div_ui( n2, n2, 2 );
}
else {
/* 奇数なら3を掛け1を加え、2で割る */
mpz_mul_ui( n2, n2, 3 );
mpz_add_ui( n2, n2, 1 );
mpz_div_ui( n2, n2, 2 );
}
}
mpz_add_ui( n, n, 1 );
}
mpz_clear( n );
mpz_clear( n2 );
mpz_clear( max_n );
return( 0 );
}
以前のプログラムは固定長整数を用いていたため、オーバーフローの問題を抱えていました。多倍長演算ライブラリGMPを使用するように修正したため、オーバーフローの問題は解決しました。
64bit符号なし整数を使用したプログラムを実行した所、12,327,829,502までの値ではすべて1に帰結してコラッツ予想が成り立つ事が確認できました。12,327,829,503を計算すると途中でオーバーフローして確認が出来ていません。1兆以下の範囲で計算させたところ、時間は約45時間かかりました。この間、17,121個の数値においてオーバーフローが確認されました。意外と計算時間が掛かりませんので、更に広い範囲まで機械的に探索させることもそれほど難しくないかもしれません。ただしオーバーフロー問題がありますから、64bitよりも更に大きな数値を扱える仕組みを用意しないといけません。
1996年時点で4兆までの値でコラッツ予想が正しい事が確認されているそうです。おそらく現在ではもっと大きな値まで確認されている事でしょう。
(2012/2/21追記)
オーバーフローしないようにGMPを使用するように修正しました。また、多少の高速化として、奇数であれば3倍して1を加えたあとの偶数奇数判定を省いています。奇数を奇数倍して奇数を加えれば偶数になることは自明だからです。
このプログラムで1兆以下を検証し、コラッツ予想が成り立つことを確認しました。しかし多倍長演算はかなり重いようで、Athlon 64 X2 5600+(2.9GHz)で約92時間掛かりました。一応、4兆までは確認したいと思うのですが、単純に考えて16日ほど掛かることになりそうです。
(2012/4/11追記)
4兆以下まで検証し、コラッツ予想が成り立つことを確認しました。計算時間ですが、計測に使用した/usr/bin/timeコマンドが桁あふれを起したようで382,885秒(約100時間)と極端に小さい時間を示しています。実際には300時間以上掛かっていたと思います(topコマンドによる観測)。
4兆まで確認されているというのは1996年出版の「フェルマーの最終定理に挑戦(ISBN:978-4816319334)」に記載されていたことですが、この書籍は一般向けのものですので実際に計算が行われたのはその数年前、おそらくは1990年代前半のことではないかと推測されます。その頃、パソコン向けのCPUは16bitの80286や68000が主流でした。クロックも10MHz程度です。この程度のCPUでは4兆以下を確認するのは現実的ではなかったでしょう。おそらくはスーパーコンピュータを使用したものと思われます。それから20年が経って、同じ内容の計算を行うのに、市井の一市民が購入できる安価なパソコンで行えるというのは、本当に感慨深いものがあります。
(2020/4/25追記)
ソースコードを少し整理しました。
(2021/11/1追記)
数学者の密室 - ７章 Collatz 予想 (E16 The 3x+1 problem)を参考に、プログラムを少し修正しました。小さい数から順に確認していくと、偶数は2で割って元の数より小さくなるので既に検証済みとして省いてよいのに加え、4n+1型の奇数は3倍して1を加えると12n+4になり、これは2で2回割って3n+1となる。元の4n+1よりも小さいのは自明なので、これも検証不要。結果、4n+3型の奇数のみ検証すればよいということです。
このプログラムで10兆以下の範囲でコラッツ予想の検証を行いました。使用したマシンのCPUはCore i5 M480(2.67GHz)です。4コアですので、実際には1兆ずつの範囲で区切って10プロセスで検証しました。こういうことが出来るように、開始値と終了値をコマンドラインから指定できるようにしたんですよね。
結果は10兆以下の全ての数でコラッツ予想が成り立つことを確認できました。計算時間は合計で737時間でした。実時間としては大体10日くらいで完了しましたので、このペースなら100兆以下の検証も不可能ではなさそうです。