I read about triangle numbers in book by Clifford Pickover, I forget which one.

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]

In reply to Triangle Numbers by YuckFoo

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.