#!/usr/bin/perl

use strict;
#use warnings; # gotta ignore the deep recursion warnings


my %lcache;


sub collatz {
    my $n = shift;

    if ($n == 1) {
    return 1;
    }

    if (exists $lcache{$n}) {
    return $lcache{$n};
    }

    my $ret;
    if ($n % 2 == 0) {
    $ret = collatz($n / 2);
    }
    else {
    $ret = collatz((3 * $n) + 1);
    }

    $lcache{$n} = $ret + 1;
    return $ret + 1;
}

my $m = 0;
for (my $i = 1; $i < 1000000; $i++) {
    my $l = collatz($i);
    if ($l > $m) {
    $m = $l;
    print 'Found a chain of length ', $l, ' for ', $i, "\n";
    }
}