http://qs1969.pair.com?node_id=161681

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