comment on

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
[download]

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

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Just another Perl shrine
	PerlMonks