3n+1問題

なんだかおもしろそうなんで反応


screenshot3n+1問題 - みずぴー日記


問題の定義は以下。

  • もし現在の値が1なら、終了する
  • もし現在の値が偶数なら、半分にする
  • もし現在の値が奇数なら、3倍して1を足す

という操作を与えられた数値に対して繰り返す。例えば10が与えられた場合には、

10 5 16 8 4 2 1

となる。どんな入力に対しても、最終的には1になると思われる。この問題では、初期値が1になるまでの系列の長さを求める。この例の場合には、系列の長さはもちろん7である。

プログラムへの入力として大小2つの整数が与えられる。この2つの数値の間にある全ての数に対して1になるまでの系列の長さを求め、その最大値を出力するようなプログラムを書け。

サンプル入力:

1 10
100 200
201 210
900 1000

出力:

20
125
89
174

なんとなく再帰でやってみた

use strict;
use warnings;
use Perl6::Say;
use List::Util qw/max/;

{
    no warnings 'recursion';
    sub get {
        my $val   = shift;
        my $count = shift || 1;
        return $count if $val == 1;
        get($val % 2 ? $val*3+1 : $val/2,++$count);
    }
}

while ( my $in = <> ) {
    my ($s,$e) = split / / , $in;
    say max map get ($_) , $s .. $e;
}

say、max、map、getが並んでるのがなんだか美しい。いや、まぁごめんなさい。

しかし再帰で100回?以上関数を呼び出すと「Deep recursion on subroutine "main::get"」という警告がでるのは若干余計なお世話な気がする。