高部あいちゃんとコラッツの予想

コラッツの予想が何のことか分からないけど、コラッツの予想をするページ。

コラッツの予想

任意の自然数n(1,2,3...)に対して、nが奇数なら3倍して1を足します。偶数なら2で割ります。 これを繰り返すと有限回で1になるという予想です。

n=2の場合、2は偶数なので2で割って1になります。
n=3の場合、3は奇数なので3を掛けて1を足し10。10は偶数だから2で割って5、そのあと16→8→4→2→1となって1になります。
nが7ならば、7→ 22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1で、長い道のりを経て1になります。

なんでコラッツの予想なの

高部あいさんとコラッツの予想がどこでリンクするのか、と聞かれれば...

高部あいさんのラジオ(2006年12月29日放送分)のポッドキャストをぼけーっと見ていると、

数学、楽しくないですかぁ？　なんか。答えが1つだしぃ、なんか、いろいろ、1つ、解き方を知ってればぁ、 応用とかいろいろできて、凄い楽しいんですね、私的に。

(中略)

たぶん、解き方をちゃんと、マスターして、応用問題、凄い難しい応用問題を問題を解くとぉ、 中ぐらいのレベルの応用問題がすごい簡単に感じると思うのでぇ、 難しいのにどんどんチャレンジしていったほうが、いいと思いますね。

このようにおっしゃっております。 数学のまったくダメな私は、この言葉に深く感銘を受けたので、 凄い難しい応用問題であるコラッツの予想にチャレンジしようと思ったわけです。

しかも、コラッツの予想を証明することができれば、500ドルいただけるそうです。 1ドルを119円で計算すると59500円になります。 これで高部あいさんの写真集(@2625円)を買うと22冊買えるわけですよ。

C言語でコラッツの予想

コラッツの予想で遊ぶプログラムです。 でっかい数値を扱えるようにunsigned __int64型を使っています。 VC++2005ならこのままでコンパイルできるはずです。

C99なら _UI64_MAXをULLONG_MAXに、 __int64をlong longに、 printfの%I64uを%lluに、 それぞれ直してください。 使い方が悪いのかもしれませんが、VC++2005だと正しく表示してくれません。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define COUNT _UI64_MAX
#define OVERFLOW (_UI64_MAX / 3 - 1)
/* コラッツの予想を行う。(64ビット)
 * 引数は自然数(1以上)
 * 戻り値はリピート回数(エラーのとき-1(0xFFFFFFFFFFFFFFFF))
 * */
unsigned __int64 collatz(unsigned __int64 n)
{
    unsigned __int64 c = 1;
    
    while (n != 1) {
        c++;
        if (n % 2) {
            if (n > OVERFLOW) return -1;//オーバーフロー
            n = 3 * n + 1;//奇数
        } else {
            n /= 2;//偶数
        }
        printf("%I64u ", n);
    }
    return c;
}
main()
{
    unsigned __int64 n, c;
    
    for (n = 1; n < COUNT;  n++) {
        printf("%I64u : ", n);
        c = collatz(n);
        printf("%s(%I64u回)\n", c == -1 ? "オーバーフロー" : "○", c);
        if (c == -1) break;
    }
}