コラッツの予想を検証する

コラッツの予想とは以下のようなものです。予想ですので、まだ証明はなされていません。

任意の自然数に対して、その数が奇数なら３倍して１を加える。偶数なら２で割る。この処理を繰り返せば必ず最後には１になる

プログラムはほぼ定義通りに作っていますが、いくつか工夫した点があります。

まず、計算中に最初の値より下回った場合はそこで終了するようにしています。これは、小さな数字から順に調べていくようにしているため、最初の値以下の数字は既に検証が済んでいるためです。更に言えば、定義より偶数は必ず最初に2で割られて最初の値より下回る事になりますので、奇数のみを調べています。プログラムは3から始めていて2を調べていませんが、2の場合は自明であるという事で省いています。

また、コンピュータで計算できる値の範囲は有限なため、途中でオーバーフローする場合があります。その場合は、そこで中止するようにしています。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main( int ac, char *av[] )
{
    unsigned long long  n, n2, max_n;

    /*  コマンドラインから探索範囲を決定する    */
    if( ac < 2 )
        return;
    max_n = strtouq( av[1], NULL, 10 );

    /*  探索範囲の数を調べる    */
    for( n = 3; n <= max_n; n += 2 ) {
        n2 = n;
        /*  n2がn以下になれば計算終了   */
        while( n2 != 1 && n2 >= n ) {
            if( n2 % 2 == 0 ) {
                /*  偶数なら2で割る */
                n2 /= 2;
            }
            else {
                /*  奇数なら3を掛け1を加える    */
                if( n2 * 3 + 1 < n2 ) {
                    printf( "%qu Overflaw\n", n );
                    break;
                }
                n2 = n2 * 3 + 1;
            }
        }
    }
}

プログラムを実行した所、12327829502までの値ではすべて1に帰結する事が確認できました。12327829503を計算すると途中でオーバーフローして確認が出来ていません。1兆以下の範囲で計算させたところ、時間は約45時間かかりました。この間、17121個の数値においてオーバーフローが確認されました。意外と計算時間が掛かりませんので、更に広い範囲まで機械的に探索させることもそれほど難しくないかもしれません。ただしオーバーフロー問題がありますから、64bitよりも更に大きな数値を扱える仕組みを用意しないといけません。

1996年時点で4兆までの値でこの予想が正しい事が確認されているそうです。おそらく現在ではもっと大きな値まで確認されている事でしょう。

コラッツの予想を検証する

コラッツの予想を検証する

訂正