未分類

【定義は易しいのに】コラッツの問題【まだ未解決問題】

コラッツの問題とは…

適当な自然数nを

  • 偶数なら2で割る
  • 奇数なら3倍して1加える

という動作を繰り返したら必ず最終的には1になる。

という予想である。他の未解決問題と比べても単純明快であり、おそらく小学生でも理解できる内容だが未だに解決されていない問題である。
1937年にドイツの数学者、ローター・コラッツが問題を提起し、その後半世紀以上も解かれていない。解決者には500ドルの賞金を与えられるというので解いてみてはいかがだろうか?

例としてn=10としよう10は偶数なので5となる。次に5は奇数なので16となる。16は偶数なので8、同様に繰り返し、1となる。この動作において2のべき乗が出てきたらその後きれいに1へと続く…
とまあ、こういう単純な計算は人間がやるよりコンピューターがやったほうがいい。実際今日までにコンピューターで計算させ、\( 5 \times 2^{60} \)までコラッツの問題は正しい(最終的に1になる)とされている。\( 5 \times 2^{60} \)は19桁の数字であり(約576京)、一般のpcではそこまでの計算はできないが\( 2^{32} \)ぐらいまでは計算できると思うので実際にコラッツの問題が途中まで正しいのを自分の目で確かめてもらいたい。

di
di
私のパソコンだとだいたい1億までは調べられたよ!

以下サンプルコードであり、初期値はa=100000となっているのでここを変えればそれ以上の数も調べることができる。

#include<stdio.h>
int main(void){
	long a=100000,m;
	for(long n=3;n<=a;n+=2){
		m=n;
		while(m!=1){
			if(m%2==0){
				m/=2;
			}else{
				m=m*3+1;
			}
		}
	}
	printf("n <= %lu :not found\n",a);
}