Problem 14


14問目。コラッツ数列(?)で100万以内の数字で最も数列が長くなるものを求める。
普通に解くと1分強かかってしまったので、すべての数列の長さを記録しておき、
数字が記録していた数になったら、記録した数にそれまでの回数を加算するという
ことにしました。つまり 10だと初めに 2で割ると5になるから、2で割った 1回に
5の場合の数列の長さを足すということ。これで8秒ほどで解けました。

#!/usr/bin/perl
use strict;
use warnings;

my %collatz;
my ($max, $max_index) = p14(1000000);
print "max is ", $max, " max index is ", $max_index, "\n";

sub p14
{
  my ($limit) = @_;
  my ($max, $max_index) = (0, 0);
  for my $i(1..$limit){
    my $count = count_collatz_number($i);
    ($max, $max_index) = ($count, $i) if $max < $count;
    $i++;
  }

  return ($max, $max_index);
}

sub count_collatz_number
{
  my ($num) = @_;
  my $count = 0;
  my $num_copy = $num;

  while ($num != 1) {
    if( exists $collatz{$num} ){
      $collatz{$num_copy} = $count + $collatz{$num};
      return $collatz{$num_copy};
    }
    $num = ($num % 2) ? (3 * $num + 1) : ($num / 2);
    $count++;
  }
  $collatz{$num_copy} = $count + 1;
  return $count + 1;
}