3x+1 問題

テスト9科目連続勝ち抜き戦に無事勝利を収め、ラスボスまで時間があるから息抜きがてらプログラミングで遊んだ。


オートマトンの授業で教えてもらった 3x+1 問題を実際にやってみた。

一応説明すると、

2以上の自然数xに対して、偶数だったら2で割り、奇数だったら3倍して1を足す、という操作を繰り返してみる。

x=2,3,4,5……とやってみると、最後に必ず１になる。

ここで、どんなに大きい自然数xでもいずれ１になるのかどうか。

という問題。


今のところ、最後に１にならない自然数は見つかっていない。


全ての自然数がいずれ１になることを証明するか、１にならない自然数を見つけるかすればもうガッポガッポである。




と、意気込んでプログラム書き始めたけど、瞬間的に組みあがってしまった。

ノートパソコンじゃあんまり大きい数まで調べられない。

#include <stdio.h>
#define N 100000

int main(void)
{
 unsigned long int i,j;

 for(i=1;i<=N;i++){
  j=i;
  while(j!=1){
   if(j%2)
    j=3*j+1;
   else
    j/=2;
  if(j<i)
   break; 
 }

  printf("%d:OK¥n",i);
 }
  
 return 0;
}