Perl: the Markov chain saw PerlMonks

### Comment on

 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!
• 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.
• 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
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2018-04-23 19:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (85 votes). Check out past polls.

Notices?