Perl: the Markov chain saw PerlMonks

### Triangle Numbers

by YuckFoo (Abbot)
 on Apr 24, 2002 at 17:31 UTC ( #161681=CUFP: print w/ replies, xml ) Need Help??

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

Comment on Triangle Numbers
Replies are listed 'Best First'.
Re: Triangle Numbers
by particle (Vicar) on Apr 24, 2002 at 19:22 UTC
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";
}
}
Update: changes as per YuckFoo (below)

Update 2: always returns an array of length three (below)

~Particle ;Þ

Good ideas particle, glad to see'em. This algorithm generates a sum of triangle numbers, but not necessarily a sum of _three_ triangle numbers. According to this, 26=21+3+1+1. But whole numbers can all be written as a sum of three tnums, 26=1+10+15. I think it would take some ugly backtracking to get yours to conform. Or else something clever.

Update: Particle, that does it, real slick, not sure why I thought it would have to get ugly. I like it!

YuckFoo

This algorithm generates a sum of triangle numbers, but not necessarily a sum of _three_ triangle numbers
EGAD! you're right. i've fixed it to generate a list of three or less (i think.) if you want precisely three, i'll have to do a little more thinking.

Update: unless of course zero is valid. i can't see how it's not, because 1 must be 1, 0, 0. so i'll update my code (once more) to reflect that.

~Particle ;Þ

Re: Triangle Numbers
by HollyKing (Pilgrim) on Apr 25, 2002 at 17:22 UTC

Well I can't add much to the Perl solutions given by YuckFoo and particle. Heck, I'm having fun just working through them to understand the code and learn some more.

I do find Triangle Numbers interesting though. Here's a bit more about them on MathWorld. Extend the triangles into the third dimension and you get Tetrahedral Numbers. I wonder if a similar statement could be made with tetrahedral numbers.

Owl looked at him, and wondered whether to push him off the tree; but, feeling that he could always do it afterwards, he tried once more to find out what they were talking about.

I'm looking at triangular and tetrahedral numbers for a paper for my Computational Number Theory class. If you look at how many triangular numbers (1/2*n*(n+1) n in N) are tetrahedral numbers (1/6*n*(n+1)*(n+2) n in N) you find that there are only 5. 5?!?! Everyone I've talked to thought there would be an infinite number of them. But why restrict ourselves to 3-d? Given any number n in a dimension d we can find the d-th dimensional analogue of the n-th triangular number given by binomial(n+d-1, d). Then things start to get strange... Robert Weston OSU Math Major westonr at onid dot orst dot edu
Re: Triangle Numbers
by Jobby (Monk) on Jul 26, 2002 at 01:36 UTC

Incidentally, the formula for the nth triangular number is actually 1/2*n*(n+1) rather than the 5*n*(n+1) given above.

Now we *can* prove that the sum of two consecutive triangular numbers is a square number:

1/2*n*(n+1) + 1/2*(n+1)*(n+2)
=1/2*(n+1)*(2n+2)
=(n+1)^2

Thought I was going nuts for a second there :)

You missed the decimal point in front of the 5.
which one is right
Re: Triangle Numbers
by ambrus (Abbot) on Oct 24, 2013 at 15:31 UTC

Create A New User
Node Status?
node history
Node Type: CUFP [id://161681]
Approved by particle
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (10)
As of 2015-08-28 18:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?