コラーツの予想とは、ある自然数xが偶数であるとき「xを2で割る」、奇数であるとき「xに3をかけて1を加える」という計算を、出た答えでまた同様に繰り返していくと「最終的に1になる」というモノである。これはまだ証明されてない超難解な問題のうちの1つであるが、あまり知られてないようだ。
このプログラムを作った理由は数学好きなためだけである。
| Program |
/*
Author : Ken Bise
Date : 20050110
Comment: 入力した自然数がコラーツの予想になるか計算する。
*/
#include<stdio.h>
main()
{
char line[10000000];
unsigned long c;
int i=0;
printf("自然数を入力せよ ");
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &c);
while( c != 1 ){
if( c % 2 == 0 ){
printf("偶数 %d\n",c);
c = c / 2;
i++;
}
else{
printf("奇数 %d\n",c);
c = ((c * 3) + 1) / 2;
i++;
}
}
printf("\n回数 %d で %d\n",i,c);
}
|
自分で自然数を決めて確かめることが出来るプログラムです。1つ目のプログラム。
次のプログラムがこのプログラムを作り直したものである。
| Program |
/*
Author : Ken Bise
Date : 20050111
Comment: 自然数を総当たりで次々と計算して行く。
*/
#include<stdio.h>
#define MIN 2
#define MAX 1000000000
main()
{
unsigned long c = MIN;
unsigned long i;
while( c != MAX ){
i = c;
while( i != 1 ){
if( i % 2 == 0 )
i = i / 2;
else
i = ( i * 3 + 1 ) / 2;
}
c++;
}
printf("%d\n",c);
}
|
1つ目のプログラムを基に書き換えた2つ目のプログラム。
MINの値からMAXの値まで総当たりで計算して行く(2が終わったら次。終わったら次...)
いつかどこかでオーバーフローが発生すると思うので一先ず10億までは計算可能(調べるの面倒)。
1億分で4分ほどなので、上のプログラムは10億だから1時間も放置すれば処理が終わると思います。
| Program |
/*
Author : Ken Bise
Date : 20050523
Comment: ある数nを計算するとき、総当たりだとn-1までは証明されていることから、
nより小さくなったら1になることが成立することを利用したプログラム。
*/
#include
|
計算スピードは抜群に上がったけど、計算できる最大値が変わってないので意味無し。
桁数増やそうかな。固定とか浮動小数点でやってもいいのか疑問。