#! /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 less # 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 decomposition # 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