好きな正整数に対して,「偶数なら2で割り,奇数なら3倍して1加える」という操作を繰り返すと最後には$1$に到達することが経験的に知られている.たとえば$3$からはじめてこの操作を繰り返すと$3\to 10\to 5\to 16\to 8\to 4\to 2\to 1$というステップを経て$1$に到達する. 今のところ反例($1$に到達しない正整数)は見つかっていないが,任意の正整数に対して上の主張が成り立つかどうかについては未解決問題である.コラッツの問題,角谷の問題,3n+1問題などと呼ばれる. ここでは実際に正整数を受け取って$1$に到達するまで上の操作を自動的に繰り返すプログラムを作成しよう.


問題


標準入力から正整数$x_1$を読み込み,以下の漸化式にしたがって$x_2, x_3, …$を順に求めて標準出力に書き出し,$x_i = 1$となったら反復を終了するプログラムを作成せよ.

ただし,プログラムは以下の仕様を満たすこと.

  1. 入力される整数$x_1$が$2 \leq x_1 \leq 100000$を満たさない時は,Errorと表示して終了する.
  2. $x_i$($i = 1, 2, …$)の値を1行ずつ表示せよ.入力された値($x_1$)を表示し忘れないように留意せよ.
  3. $x_i = 1$になった時は,その計算結果1を表示したのち,OKと表示してプログラムを終了せよ.
  4. $x_{100}$まで計算しても値が$1$にならない場合は,$x_{100}$の値を表示したのち,そのままプログラムを終了せよ.このときはOKと表示しないこと.
  5. 各表示は標準出力に出力し,それぞれ末尾には改行文字\nを付けること.

実行例


#は標準入力,>は標準出力を表す.

# 3
> 3
> 10
> 5
> 16
> 8
> 4
> 2
> 1
> OK
# 10
> 10
> 5
> 16
> 8
> 4
> 2
> 1
> OK
# 27
> 27
> 82
> 41
> 124
... (途中省略) ...
> 70
> 35
> 106

手順例


問題を分解して考える.

  1. 標準入力から正整数$x_1$を読み込む
  2. $x_{i+1}$ を繰り返し計算
  3. $x_{i+1}$ を出力

0. 準備

これまでと同様に,まず,確実に必要と思われるC言語のメインの構造を作ってみる.

#include <stdio.h>

int main()
{
  return 0;
}

1. 標準入力から正整数$x_1$を読み込む

次に,読み込み部分を考える.

#include <stdio.h>

int main()
{
  scanf("%d", &xxx);
  return 0;
}

2. 繰り返し計算

次に,計算する部分を考える.

#include <stdio.h>

int main()
{
  scanf("%d", &xxx);
  if(xxx ### ){  // 偶数の場合

  }
  else{

  }
  return 0;
}
#include <stdio.h>

int main()
{
  scanf("%d", &xxx);
  if(xxx ### ){  // 偶数の場合
    xxx /= 2
  }
  else{
    xxx *= 3 + 1
  }
  return 0;
}
#include <stdio.h>

int main()
{
  scanf("%d", &xxx);
  for(;;){
    if(xxx ### ){  // 偶数の場合
      xxx /= 2
    }
    else{
      xxx *= 3 + 1
    }
  }
  return 0;
}

3. $x_{i+1}$ を出力

#include <stdio.h>

int main()
{
  scanf("%d", &xxx);
  for(;;){
    if(xxx ### ){  // 偶数の場合
      xxx /= 2
    }
    else{
      xxx *= 3 + 1
    }
    printf("%d", xxx);
  }
  return 0;
}

条件


4. 入力される整数$x_1$が$2 \leq x_1 \leq 100000$を満たさない時は,Errorと表示して終了する.


5. 入力された値($x_1$)を表示し忘れないように留意せよ.


7. $x_i = 1$になった時は,その計算結果1を表示したのち,OKと表示してプログラムを終了せよ.

    if (x == 1) { // 終了条件
      printf("%d", xxx);
      printf("OK");
      break;
    }

8. $x_{100}$まで計算しても値が$1$にならない場合は,$x_{100}$の値を表示したのち,そのままプログラムを終了せよ.このときはOKと表示しないこと.


9. 各表示は標準出力に出力し,それぞれ末尾には改行文字\nを付けること.


手順例まとめ

繰り返しになるが,この課題の上記参考プログラムは,あえていくつか間違いを含んだ状態で記載している.わからない場合は,コンパイルや実行をして,実際のエラーメッセージや出力結果を参考にプログラムの間違いを修正すること.


参考情報



for文やwhile文による繰り返し処理,continue文,break



余談


コラッツの問題はコンピュータを用いたシミュレーションにより,$20 \times 2^{58}$($\approx 5.76 \times 10^{18}$)までの値に対しては最終的に$1$に到達することが確認されている.

プログラムを確実に停止させるため,反復は100回までという制限を設けた.この制限を緩和もしくは撤廃すれば,(このプログラムが対応できる範囲の)どんな自然数を入力しても,有限回の操作で1に到達することを自分の目で確認できるであろう.


参考文献