#! /usr/bin/perl -w

use strict;

# trinum(n) returns the nth triangular number
sub trinum { my ($n) = @_; return $n * ($n+1) * 0.5; }

# prev_trinum(n) returns the RANK OF the greatest triangular number le
+ss
#  than n.
# Code blatantly ripped off from Limbic~Region [id://399054]
sub prev_trinum
{
    my $num = shift;
    my $x = ( sqrt( 8 * $num + 1 ) + 1 )/ 2;
    my $t = int $x;
    return $t == $x ? 0 : --$t;
}

# trinum_decomp(n) tries to find a three-triangular-number decompositi
+on
#  of n.  Based on L~R's method from the post cited above, but
#  enumerates trinums rather than guessing.
sub trinum_decomp
{
    my ($n) = @_;

    my $prev = &prev_trinum($n);
    return ($n, 0, 0) unless $prev;

    while($prev) {
        my $triprev = ($prev * $prev + $prev)/2;
        my $diff = $n - $triprev;
        my @tail = &twonum_decomp($diff);
        if(defined $tail[0]) {
            return ($triprev, @tail);
        }
        $prev--;
    }
    warn "Can't find trnum decomp for $n\n";
    return (-1, -1, -1); # ugly
}

# twonum_decomp(n) tries to find a two-triangular-number decomposition
#  of n.  If such a decomposition does not exist, returns undef.
sub twonum_decomp
{
    my ($n) = @_;

    my $prev = &prev_trinum($n);
    return ($n, 0) unless $prev;

    while($prev) {
        my $triprev = ($prev * $prev + $prev)/2;
        my $i = 1; my $tri_i = ($i * $i + $i)/2;
        do {
            if($tri_i + $triprev == $n) {
                return ($tri_i, $triprev);
            }
            $i++; $tri_i = ($i * $i + $i)/2;
        } while($triprev + $tri_i <= $n);
        $prev--;
    }
    return undef;
}

my $target = $ARGV[0] || 314159;
print join(',', &trinum_decomp($target));

__END__
mjolson@riga:~/devel/scratch
Wed Oct 13-18:38:42 583 >time ./trinum 987654321
987567903,14028,72390
real    0m0.089s
user    0m0.060s
sys     0m0.000s

mjolson@riga:~/devel/scratch
Wed Oct 13-18:18:25 578 >time ./limbic_trinum 987654321
987567903, 14028, 72390
real    0m0.106s
user    0m0.090s
sys     0m0.000s
[download]