#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use Data::Dumper;
use constant MAX => 300000;
my %cache;
sub collatz_seq {
my $input = shift;
my $n = $input;
my @result;
while ($n != 1) {
if (exists $cache{$n}) {
push @result, @{$cache{$n}};
last;
} else {
my $new_n = $n % 2 ? 3 * $n + 1 : $n / 2;
push @result, $new_n;
$cache{$n} = [$new_n, @{$cache{$new_n}}]
if defined ($cache{$new_n}) and $n < MAX;
$n = $new_n;
}
}
$cache{$input} = [@result] if $n < MAX;
return @result;
}
my @long_seqs;
for my $num (1..1000000) {
my @seq = ($num, collatz_seq $num);
push @long_seqs, [ $num, scalar @seq] if scalar @seq > 400;
}
@long_seqs = sort { $b->[1] <=> $a->[1]} @long_seqs;
say "$_->[0]: $_->[1]" for @long_seqs[0..19];
# say "@{$cache{$long_seqs[0][0]}}";
####
real 0m22.596s
user 0m21.530s
sys 0m1.045s
##
##
use strict; use warnings; use feature 'say';
use Data::Dumper;
use MCE::Map;
my @output = mce_map_s {
my $input = $_;
my $n = $input;
my @result = $input;
while ( $n != 1 ) {
$n = $n % 2 ? 3 * $n + 1 : $n / 2;
push @result, $n;
}
return [ $input, scalar @result ];
} 1, 1000000;
MCE::Map->finish;
@output = sort { $b->[1] <=> $a->[1] } @output;
say sprintf('%s : length %s', $_->[0], $_->[1]) for @output[0..19];
##
##
real 0m4.322s
user 0m27.992s
sys 0m0.170s
##
##
my %cache;
my $sets = my $gets = 0;
sub cache_has { $gets++; exists $cache{$_[0]} }
sub cache_set { $sets++; $cache{$_[0]} = $_[1] }
sub cache_get { $gets++; $cache{$_[0]} }
##
##
Sets: 659,948
Gets: 16,261,635