use strict;
use warnings;
use feature 'say';
use Data::Dump 'dd';

use Time::HiRes 'time';
my $t = time;

my %cache = ( 1 => [ 1, 1, undef ]);
#
# [ seq_length, start_num (same as key), next_num ]
#

sub _cache_collatz {
    my $n = shift;
    return if exists $cache{ $n };
    my ( @tmp , $new_n );
    while ( !exists $cache{ $n }) {
        $new_n = $n % 2 ? 3 * $n + 1 : $n >> 1;
        push @tmp, $cache{ $n } = [ -$#tmp, $n, $new_n ];
        $n = $new_n
    }
    my $d = $#tmp + $cache{ $n }[ 0 ];
    $_-> [ 0 ] += $d for @tmp
}

sub collatz {
    my $n = shift;
    _cache_collatz( $n );
    my @a = $n;
    push @a, $n while $n = $cache{ $n }[ 2 ];
    return \@a;
}

## Demo
#
# dd collatz( 23 );
# dd \%cache;
# exit( 0 );
#
##

_cache_collatz( $_ ) for 1 .. 1e6;

say "@$_[ 1, 0 ]"
    for ( sort { $b-> [ 0 ] <=> $a-> [ 0 ]} 
               @cache{ 1 .. 1e6 })[ 0 .. 19 ];
say time - $t;

__END__

837799 525
626331 509
939497 507
704623 504
910107 476
927003 476
511935 470
767903 468
796095 468
970599 458
546681 452
818943 450
820022 450
820023 450
410011 449
615017 447
886953 445
906175 445
922524 445
922525 445
6.44625306129456