Contribution for Puzzlet #028

From:  Denis Borris []

Of course, the main part of this puzzlet is finding a quick way to get all integer right triangles. I set up (for myself) a while ago what works really fast; thought I'd send it to you (keeping the typing at minimum!

For right triangles with integer sides, let: a = short leg,
b = other leg, c = hypotenuse. Then: b = a + x and
c = a + x + y (x and y being positive integers, of course).

It is a fact that:
a^2 = c^2 - (c-1)^2 if a is odd; like: a:b:c = 7:24:25
a^2 = c^2 - (c-2)^2 if a is even; like: a:b:c = 8:15:17

This provides a quick way to know "time to quit this one!".

So we can find ALL triangles by simply looping a and y;
x can ce calculated from a and y.

Combining above "juicily(!)" leads to maximum y (my):
my = int[sqrt(2*a^2 - 1) - a]
We then adjust my by -1 depending on a being odd or even. So we can now loop y from my to 1 in steps of -2.

As example, if a=11, then my = 4 (using equation above).
Since a is odd, then we adjust my to 3.
So the loop is y=3,1. x is calculated from each y.

100 for a = 3 to (whatever)
110 my =  int[sqrt(2*a^2 - 1) - a]
120 if a@2=1 and my@2=0 or a@2=0 and my@2=1 then my=my-1  'adjust my
130 for y = my to 1 step -2
140 x = (a^2 - 2*a*y - y^2) / (2*y)
150 if x - int(x) <> 0 then goto 190   'check if x = integer
160 b = a + x
170 c = b + y
180 print a,b,c
190 next y
200 next a

This'll get you ALL the right triangles in a jiff.

Answer to your puzzlet, keeping a < 10,000:

Thanks for this enlightening message!  I have a version of this myself.  If you do the sums, you can show that:

For odd a:  b = (a^2 - 1)/2, c = (a^2 + 1)/2
For even a: b = (a^2 - 4)/4, c = (a^2 + 4)/4

This finds all primitives such as 12,35,27, but misses some multiples such as 12,16,20. It also misses the multiple which forms the smallest answer to the puzzlet, so I am currently using a slightly slower algorithm.   Dave.


Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 22nd, 2004.