We don't bite newbies here... much PerlMonks

### Comment on

 ( #3333=superdoc: print w/ replies, xml ) Need Help??
There is a theorem by Gauss which shows that finding M as the sum of three triangle numbers is equivalent to finding 8M+3 as the sum of three odd squares. That is, if
```8M + 3 = (2A+1)^2 + (2B+1)^2 + (2C+1)^2
then
M = trinum(A) + trinum(B) + trinum(C)
The computation starts with a bigger number, but the calculations might be easier this way. I'll try it when I get a chance.

Update: Here is code that takes advantage of a few things that are known about Diophantine quadratic problems. For example, it can convert multiples of two into smaller problems. It also screens out a few factors which would make a solution impossible. In many cases, it should be faster than the brute-force triangular number search.

```# Find a triangle-number decomposition by converting to
# a Diophantine squares problem.

use strict;

# These have no quadratic residue for -1.
# If they appear as factors in M an odd number of times
# a solution is impossible.
our @screeners = (3, 7, 11, 19, 23, 31);

# The brute-force search for a quadratic solution.
# We have reduced the number as much as we can before this
# point.
my \$M = shift;
my \$top = int(sqrt(\$M));
my \$last = int(\$top/2) + 1;

my (\$i, \$j, \$rem);
for (\$i = \$top; \$i >= \$last; --\$i) {
\$rem = \$M - \$i*\$i;
\$j = int(sqrt(\$rem));
if (\$j*\$j == \$rem) {
return (\$i,\$j);
}
}
}

# How many times does \$n go into \$M?
sub countpowers {
my (\$M, \$n) = @_;
my \$powercount = 0;
while (\$M % \$n == 0) {
\$M = \$M/\$n;
++\$powercount;
}
return (\$M, \$powercount);
}

# Reduce even numbers before solving by brute force.
# Also, screen out some impossible cases.
# Don't try a full factorization for now.
my \$M = shift;
my \$powercount;
my \$multfactor = 1;

# Screen out odd impossible cases, and factor out pairs of 4k-1 fac
+tors.
foreach my \$num (@screeners) {
(\$M, \$powercount) = countpowers(\$M, \$num);
if (\$powercount % 2 == 1) {
print "Eliminating impossible case with odd-power of 4k-1 fac
+tor \$num\n";
return;
}
# In even cases, half the factors can be multiplied into the res
+ult.
\$powercount = \$powercount/2;
for (my \$i = 0; \$i < \$powercount; \$i++) {
\$multfactor *= \$num;
}
}

# Count powers of 2.  We can handle the case of odd powers of 2.
(\$M, \$powercount) = countpowers(\$M, 2);

if (\$powercount % 2 == 0) {
# Two goes in an even number of times.
if (\$powercount > 0) {
\$multfactor *=  1 << ((\$powercount)/2);
}
return (\$i*\$multfactor, \$j*\$multfactor);
}

# Two goes in an odd number of times.  Use the i+j, i-j trick.
if (\$powercount > 1) {
\$multfactor *=  1 << ((\$powercount - 1)/2);
}
return ((\$i + \$j)*\$multfactor, (\$i - \$j)*\$multfactor);
}

my \$M;
\$M = (\$#ARGV >= 0)? \$ARGV[0] : 987654321;

# Convert from a triangle-number problem to a square-number problem.
my \$M2 = \$M*8 + 3;

# The top-level loop will try odd squares by brute force.
my \$top = int(sqrt(\$M2));
\$top = \$top - 1 if (\$top % 2 == 0);  # start with odd.
my \$last = int(\$top/2) + 1;
my \$k;
for (\$k = \$top; \$k >= \$last; \$k -= 2) {
my \$M3 = \$M2 - \$k*\$k;
if (\$i) {
# Convert solution back to triangle-numbers.
my \$new_i = (\$i - 1)/2;
my \$new_j = (\$j - 1)/2;
my \$new_k = (\$k - 1)/2;
print "Solution: triangle numbers \$new_i, \$new_j, \$new_k\n";
my \$tri_i = (\$new_i+\$new_i*\$new_i)/2;
my \$tri_j = (\$new_j+\$new_j*\$new_j)/2;
my \$tri_k = (\$new_k+\$new_k*\$new_k)/2;
my \$sum = \$tri_i + \$tri_j + \$tri_k;
print "Verifying \$tri_i + \$tri_j + \$tri_k = \$sum = \$M\n";
exit(0);
}
}

In reply to Re: Triangle Numbers Revisited by tall_man
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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (19)
As of 2013-12-12 09:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?