最近、twitterの方で話題になっていた、こんな問題
任意の0でない自然数 n をとり、
* n が偶数の場合、n を 2 で割る
* n が奇数の場合、n に 3 をかけて 1 を足すという操作を繰り返すと、有限回で 1 に到達する
2時間あまりペン先をいじくり回して、論証できたー!!と思ったら実は未解決問題だったというオチでアラララ!となった問題。
論証の方は激むずなんだけど、これ、本当になりたつのかなー。というわけで成り立つかどうか調べるサンプルスクリプトをサクッと書いてみたよ。
<?php $i = 1; $k = 0; $test = 0; $flag = 0; while($i<1001){ $test = $i; $flag = 1; while($flag == 1 ){ if($buffer == 1000){ echo"$i is bad!\n"; $buffer = 0; $flag == 0; }else{ if($test == 1){ echo "$i is good!\n"; $flag = 0; $buffer = 0; }elseif($test % 2 == 0){ $test = $test/2; $buffer = $buffer+1; echo "$test,"; }else{ $test = 3*$test+1; $buffer = $buffer+1; echo "$test,"; } } } $i = $i+1; echo "mention$i\n"; }
実際に走らせてみると、1から始まって1000までの操作を再現してくれるよ。
1000までの数字では有限回(1000回)の操作で1にたどり着くみたい。やったね!
上のコードは、気に食わない人は自由に最適化してみてね!
僕のパソコン(Windows7 2GHzあたりのCPU)で走らせたところ、上のコードでも5秒くらいで計算が終わったからそこそこ快適なマシンだったら問題ないとは思うけど。