#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

my $max = shift || 1e6;
$max = 1e6 if $max < 1e6;

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

sub collatz_seq {
    my $input = shift;
    my $n = $input;
    my $result = 0;
    my $new_n;

    while ($n != 1) {
        $result += $cache[$n], last
            if defined $cache[$n];

        $n % 2 ? ( $result += 2, $new_n = (3 * $n + 1) >> 1 )
               : ( $result += 1, $new_n = $n >> 1 );

        $n = $new_n;
    }

    $cache[$input] = $result if $input < $max;
    return $result;
}

my @long_seqs;
for my $num (1..$max) {
    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];