Triangle numbers are numbers of the form 0+1+2+3...n, or .5*n*(n+1). The first few t-nums are 0, 1, 3, 6, 10, 15, 21. These are numbers of items that can be arranged in a triangle, like bowling pins.

There are many interesting features of t-nums. Adding any two consectutive t-nums is a square number (6+10, 10+15), which makes sense when you think about it.

A notable t-num is the 36th t-num, 666. Of course 36 (6*6) is itself a t-num.

What I found most fascinating was the claim that any whole number can be written as the sum of three t-nums. I'm still trying to figure out why. In the meantime I wrote this program to check it out.

The program is a bit brutish. I keep an array of t-nums that I add to as needed. To find the three addends, I binary search for the largest t-num less or equal to the target. I initialize the three numbers to this value and iterate through all possibilities to find the answer. Any suggestions to optimize the search method?

YuckFoo

#!/usr/bin/perl

   use strict;

   my (@todo) = @ARGV;
   my ($each, @nums);

   my @tris = (0, 1);

   for $each (@todo) {
      maketriangles(\@tris, $each);
      @nums = findthree(\@tris, $each);

      print "$each = ", join(' + ', @tris[@nums]), "\n";
      #print join(', ', @nums), "\n";
   }

#-----------------------------------------------------------
sub maketriangles {

   my ($tris, $num) = @_;

   while ($tris->[-1] < $num) {
      push (@{$tris}, $tris->[-1] + ($tris->[-1] - $tris->[-2] + 1));
   }
}

#-----------------------------------------------------------
sub findthree {

   my ($tris, $num) = @_;

   my ($i, $j, $k, $start);

   $start = $i = $j = $k = largeless($tris, $num);

   while ($k > 0) {
      if ($num == $tris->[$i] + $tris->[$j] + $tris->[$k]) {
         return ($i, $j, $k);
      }

      $i--;
      if ($i < 0) {
         $i = $start;
         $j--; 
         if ($j < 0) {
            $j = $start;
            $k--; 
         }
      }
   }
   return (0, 0, 0);
}

#-----------------------------------------------------------
sub largeless {

   my ($tris, $num) = @_;
   
   my $beg = 0;
   my $end = @{$tris};
   my $mid = int(($beg + $end) / 2);

   while ($mid != $beg && $mid != $end) {

      if    ($tris->[$mid] < $num) { $beg = $mid; }
      elsif ($tris->[$mid] > $num) { $end = $mid; }
      else                         { last; }

      $mid = int(($beg + $end) / 2);
   }

   return $mid;
}
[download]