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

use File::Map qw/map_anonymous unmap/;

my $size = shift || 1e6;

$size = 1e6 if $size < 1e6;  # minimum
$size = 1e9 if $size > 1e9;  # maximum

map_anonymous my $cache, $size * 2, 'shared';

# init cache with -1's, then set 0, 1, 2
substr($cache, 0, $size * 2, ( my $neg1 = pack('s', -1) ) x $size);
substr($cache, $_ * 2, 2, pack('s', $_)) for 0..2;

my @seqs;

sub collatz_seq {
    my ( $seq_beg, $seq_end ) = @_;
    my ( $n, $steps, $tmp );
    for my $input ( $seq_beg..$seq_end ) {
        $n = $input, $steps = 0;
        while ( $n != 1 ) {
            $steps += unpack('s', $tmp), last
                if ($n < $size && ($tmp = substr($cache, $n * 2, 2)) ne $neg1);

            $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
                   : ( $steps += 1, $n = $n >> 1 );
        }
        substr($cache, $input * 2, 2, pack('s', $steps)) if $input < $size;
        push @seqs, [ $input, $steps ] if $steps > 400;
    }
}

collatz_seq(2, $size); unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
    for @seqs;