Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re: Triangle Numbers

by particle (Vicar)
on Apr 24, 2002 at 19:22 UTC ( #161737=note: print w/replies, xml ) Need Help??

in reply to Triangle Numbers

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

Replies are listed 'Best First'.
Re: Re: Triangle Numbers
by YuckFoo (Abbot) on Apr 24, 2002 at 19:36 UTC
    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!


      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 ;

        1001, 0000, 0000, 1001 are the first four lines of my "God's Zone Of Zero" in Christmatics. Are you aware that every other triangle number plotted on a square grid seems to produce two straight and parallel lines on that grid? Those two straight parallel lines pass through the zone of zero in such a way that what Christmatics is calling "Joseph's stick" becomes "Judah's stick" when that line has passed through "God's Zone Of Zero". If this interests you, do a search for "Ezekiel's Two Sticks" and "Christmatics" on the web for more of my thoughts. Waldo

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://161737]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2016-10-23 06:53 GMT
Find Nodes?
    Voting Booth?
    How many different varieties (color, size, etc) of socks do you have in your sock drawer?

    Results (300 votes). Check out past polls.