Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Just off the top of my head:

In the inner while loop, it looks like you're testing each $i, $j to see if it's triangular (although I must confess, I don't really understand p_tri). Since we can enumerate triangle numbers (if Jobby is to be believed), why not iterate through those?

Edit: Are you sure you're getting correct solutions? It looks like $prev starts out as a triangular number, but then you just decrement it. (Aside: if this algorithm gives you consistently correct solutions, then the greatest triangular number lower than n is always present in n's triangular decomposition. I think.) Man, I'm an idiot. Since when is $prev a trinum?

Edit 2: Oh, I get it, p_tri returns the rank of the previous triangular number, not the number itself... although it returns zero when given a triangular number, which is weird but useful.

Edit 3: Here's the start of an implementation. It's not as fast as the code posted above (by about a factor of two, if Unix time is to be trusted), probably because it calculates a lot of trinums and makes a lot of function calls. I'm posting it more or less as a proof of concept.

Edit 4: Inlining the calls to &trinum results in slightly faster code than Limbic~Region's. Code updated, benchmarks added.

#! /usr/bin/perl -w use strict; # trinum(n) returns the nth triangular number sub trinum { my ($n) = @_; return $n * ($n+1) * 0.5; } # prev_trinum(n) returns the RANK OF the greatest triangular number le +ss # than n. # Code blatantly ripped off from Limbic~Region [id://399054] sub prev_trinum { my $num = shift; my $x = ( sqrt( 8 * $num + 1 ) + 1 )/ 2; my $t = int $x; return $t == $x ? 0 : --$t; } # trinum_decomp(n) tries to find a three-triangular-number decompositi +on # of n. Based on L~R's method from the post cited above, but # enumerates trinums rather than guessing. sub trinum_decomp { my ($n) = @_; my $prev = &prev_trinum($n); return ($n, 0, 0) unless $prev; while($prev) { my $triprev = ($prev * $prev + $prev)/2; my $diff = $n - $triprev; my @tail = &twonum_decomp($diff); if(defined $tail[0]) { return ($triprev, @tail); } $prev--; } warn "Can't find trnum decomp for $n\n"; return (-1, -1, -1); # ugly } # twonum_decomp(n) tries to find a two-triangular-number decomposition # of n. If such a decomposition does not exist, returns undef. sub twonum_decomp { my ($n) = @_; my $prev = &prev_trinum($n); return ($n, 0) unless $prev; while($prev) { my $triprev = ($prev * $prev + $prev)/2; my $i = 1; my $tri_i = ($i * $i + $i)/2; do { if($tri_i + $triprev == $n) { return ($tri_i, $triprev); } $i++; $tri_i = ($i * $i + $i)/2; } while($triprev + $tri_i <= $n); $prev--; } return undef; } my $target = $ARGV[0] || 314159; print join(',', &trinum_decomp($target)); __END__ mjolson@riga:~/devel/scratch Wed Oct 13-18:38:42 583 >time ./trinum 987654321 987567903,14028,72390 real 0m0.089s user 0m0.060s sys 0m0.000s mjolson@riga:~/devel/scratch Wed Oct 13-18:18:25 578 >time ./limbic_trinum 987654321 987567903, 14028, 72390 real 0m0.106s user 0m0.090s sys 0m0.000s

--
Yours in pedantry,
F o x t r o t U n i f o r m


In reply to Re: Triangle Numbers Revisited by FoxtrotUniform
in thread Triangle Numbers Revisited by Limbic~Region

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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others examining the Monastery: (11)
    As of 2014-08-23 11:47 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (173 votes), past polls