#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use constant MAX => 1000000;

my @cache = (0, 1, 2);

sub collatz_seq {
    my $input = shift;
	my $n = $input;
    my $result = 0;
    while ($n != 1) {
        if (defined $cache[$n]) {
            $result += $cache[$n];
            last;
        } else {
            my $new_n = $n % 2 ? 3 * $n + 1 : $n / 2;
            $result++;
            $cache[$n] = $cache[$new_n] + 1 
				if defined $cache[$new_n] and $n < MAX;
            $n = $new_n;
        }
    }
	$cache[$input] = $result if $input < MAX;
    return $result;
}

my @long_seqs;
for my $num (1..1000000) {
    my $seq_length = collatz_seq $num;
    push @long_seqs, [ $num, $seq_length ] if $seq_length > 400;
}

@long_seqs = sort { $b->[1] <=> $a->[1]} @long_seqs;
say  "$_->[0]: $_->[1]" for @long_seqs[0..19];