コラッツの問題

パソコン甲子園2007年本選の問題

正の整数に対し，

• nが偶数のときは2で割る
• nが奇数のときは3倍して1を足す

という操作を繰り返すと結果が1になる．
整数nを入力とし，結果が1になるまで繰り返される操作の回数を出力するプログラムを作成せよ．

どうやら1になることは経験的に知られているが，まだ証明されていないらしい．角谷の問題とも呼ばれるとか．

問題の難易度は高くないが，コードの「美しさ」を競うのだという．うーん．
これくらい簡単なら覚えたてLispで書けるな．えいっ．

(defun collatz (n)
  (collatz-count n 0))

(defun collatz-count (n cnt)
  (cond ((= n 1) cnt)
	((evenp n) (collatz-count (/ n 2) (1+ cnt)))
	(t (collatz-count (+ 1 (* n 3)) (1+ cnt)))))

cntで回数を記憶してnが1になるまで増やしていく．そのまんまですね．

Perlの場合，

sub get_collatz_count{
  my ($n) = @_;
  die if ($n <= 0);
  my $count = 0;

  while($n != 1){
    if($n % 2 == 0){
      $n = $n / 2;
    }else{
      $n = $n * 3 + 1;
    }
    $count++;
  }
  
  return $count;
}

美しいコードってどんなんだろう．Lispコードが酷すぎるので，ちょっと後で手直ししよう．