Highly divisible triangular number

AUTHOR

polettix

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be

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

The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

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

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

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;
}

# vim: expandtab shiftwidth=4 ft=perl6

AUTHOR

See Also