Contribution for Puzzlet #028
From: Denis Borris [firstname.lastname@example.org]
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.