好きな正整数に対して,「偶数なら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$となったら反復を終了するプログラムを作成せよ.

ただし,入力される正整数$x_1$は$2 \leq x_1 \leq 100000$を満たすと仮定してよい. プログラムは以下の仕様を満たすこと.

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

ヒント

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

余談

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

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

参考文献