i suggest using a bit vector for storage (see
vec.) use one bit per number
to store whether it's triangular or not. i'll leave it as an excersize to figure out the details of my implementation.
#!/usr/bin/perl -w
use strict;
$|++;
my $number = $ARGV[0] || die("Usage: trivec.pl number$/");
my $vecTri;
$vecTri = createTriVec( $number );
print $/, findTriCombo( $vecTri, $number );
sub createTriVec
{
my $upper = $_[0] || 99;
my $vec = "\0";
my $guess = 0;
for( my $num = 1; $guess+$num <= $upper; $num++ )
{
$guess+=$num;
vec( $vec, $guess, 1 ) = 1;
}
return $vec;
}
sub findTriCombo
{
my $vec = $_[0] || return undef;
my $num = $_[1] || return undef;
my @tris;
my $sum = 0;
push(@tris, $num, 0, 0), return "@tris" if( vec( $vec, $num, 1 ) )
+;
my $i = $num-1;
while( $i > 0 )
{
# print "<i $i>\t<s $sum>\t<t @tris>$/"; # UNCOMMENT TO SEE WHAT'S GOI
+NG ON...
if( scalar @tris >= 3 ) {
$i = $tris[0] - 1;
@tris = ();
$sum = 0;
}
if( vec( $vec, $i, 1 ) )
{
push @tris, $i;
$sum += $i;
$i = $num - $sum;
next;
}
else
{
$i--;
}
}
if( $sum == $num )
{
push(@tris, 0) while @tris < 3;
return "@tris";
}
return "not found!";
}
Update: changes as per
YuckFoo (below)
Update 2: always returns an array of length three (below)
~Particle ;Þ