最长考拉兹序列

作者：Felix Herrmann

https://projecteuler.net/problem=14

对于正整数集，定义以下迭代序列

n → n/2（n 为偶数） n → 3n + 1（n 为奇数）

使用上述规则并从 13 开始，我们生成以下序列：13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出，这个序列（从 13 开始到 1 结束）包含 10 个项。虽然尚未得到证明（考拉兹猜想），但人们认为所有起始数字最终都会到 1。

在一百万以下，哪个起始数字会产生最长的链？

注意：一旦链开始，这些项允许超过一百万。

源代码： prob014-felher.pl

use v6;

# this program takes quite a few minutes on my machine

my Int multi sub collatz(Int $n where * %% 2) { $n div 2;   }
my Int multi sub collatz(Int $n             ) { 3 * $n + 1; }

my Int sub get-length(Int $n)  {
    state Int %length{Int} = 1 => 1;
    my $result = %length{$n} // 1 + get-length collatz $n;
    %length{$n} = $result;
    $result;
}

my $max = 0;
my $start = 0;
for 1 ..^ 1_000_000 -> $n {
    say "Starting number: $n" unless $n % 10000; #just for progress
    my $length = get-length $n;

    if $length > $max {
        $start = $n;
        $max = $length;
    }
}

say "The starting number $start produces a sequence of length $max";