高度可约三角形数

作者：polettix

三角形数序列是通过将自然数相加生成的。所以第 7 个三角形数是

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

前十项是

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

让我们列出前七个三角形数的因数

1: 1
3: 1,3
6: 1,2,3,6

10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

我们可以看到，28 是第一个拥有超过五个因数的三角形数。

第一个拥有超过五百个因数的三角形数是多少？

源代码： prob012-polettix.pl

use v6;

# Minimum number of factors, defaults to challenge's request
my $t = @*ARGS.shift || 500;


# It's easy to tell triangle numbers: they are all of the form
# ($n * ($n + 1)) / 2. Hence, the factors are those of
# $n and ($n + 1), less one "2" because of the division.
#
# We'll iterate through $n, from 2 to... wherever it is needed.
#
# We use a factors_progressively_asked() function that is supposed
# to return factors but requests you to ask factors for numbers
# progressively (i.e. start from 2, then 3, 4, 5, ...). This allows
# an optimisation and is perfect in our case, because we need the
# factors for increasing values of $n.

my $max = 1;
my $n = 2;
my %previous_factors = factors_progressively_asked(2);

# Due to lazyness, we'll talk about ($n - 1) and $n instead of $n and
# ($n + 1).
while ($max <= $t) {
    $n++;
    my %this_factors = factors_progressively_asked($n);

    # Now, %previous_factors has the factors for ($n - 1), and
    # %this_factors has the factors for $n. We mix them all into
    # %previous_factors and then eliminate one "2" to cope with the
    # division.
    %previous_factors{$_} += %this_factors{$_} for %this_factors.keys;
    %previous_factors{2}--; # divide by 2

    # Now, we count the number of different factors
    my $p = 1;
    $p *= $_ for %previous_factors.values.map({ $_ + 1 });

    # a little feedback
    say "$n $p ($max)" unless $n % 100;

    # prepare for next iteration: update $max and save %this_factors
    $max = $p if $max < $p;
    %previous_factors = %this_factors;
}

say 'result: ', ($n * ($n - 1)) / 2;

# In rakudo, the "is copy" is needed because of a known bug
# as of Aug 24th, 2009. Otherwise, the @primes.push($x) gets
# "confused".
sub factors_progressively_asked ($x is copy) {
    state @primes;
    state %factors_for;
    my $result;

    if (%factors_for{$x}:exists) {
        $result = %factors_for{$x};
    }
    else {
        for @primes -> $p {
            if ($x % $p) == 0 { # Bingo! A divisor!
                # Now, $p is prime, and $x / $p is surely into %factors_for
                # because we're calling this function progressively, so
                # we're done.
                $result = [ $p, %factors_for{$x / $p}.list ];
            }
        }
        if (! $result) { # Ok, there's a new prime in town
            @primes.push($x);
            $result = [ $x ];
        }
        %factors_for{$x} = $result;
    }

    # Return as a hash of (factor, occurrences) pairs
    my %factors;
    %factors{$_}++ for $result.list;
    return %factors;
}