An algorithm to generate all the perfect right triangles

[TheBigDog]

The “1:4499 2:2249 8:1123 9:822 18:415 25:715 …” count of PERTs by J excludes triangles with side lengths that are not relatively prime such as 6x8x10. It would not exclude triples that are not pairwise relatively prime, such as (2,6,9), although I suspect (but haven’t verified) that no such right triangles exist. I suspect that A & B are relatively prime for all PERTs.

OK. I was looking at the same idea that there are no common factors among any legs of a PERT. I have not found any that violate that rule yet, but have not examined a very big set yet.

 

Bill

[CraigD]

I’m returning to this thread after a couple of weeks inactivity, in which many PERT-related posts appeared in 1343, including Pyrotex’s neat observation that the possible values of the PERT Delta (J) (the difference between the long leg and the hypotenuse) are given by J=2K^2 and (2K-1)^2, some fascinating graphical looks at patterns and “weird clustering” among A,B,C and J.

 

So far, these insights have allowed me to improve the PERT / ERT (non-prime exact right triangle) algorithm in post #1 so that its computation efficiency is improved from slightly over N^2 iterations per A, to N^(3/2), allowing my modest Windows laptop and its number-crunchingly unspectacular Cache MUMPS interpreter to churn out the first 20,000 PERTs in 12 seconds, and the first 1,000,000 in a little over 30 minutes. Here’s an interactive version of the code:

r XJ,XGCD
s:J=J1 K1=K1+1,J1=K1*K1*2 s:J=J2 K2=K2+1,J2=K2*2-1**2 s J=$s(J1>J2:J2,1:J1) ;XJ: return next J given K1,K2,J1,J2,J
f  q:'N2  s GCD=N2,N2=N1#N2,N1=GCD ;find GCD of N1 & N2
s A=0,X="" f A=A+1:1 q:$l(X)  s (K1,K2,J1,J2,J)=0 f  x XJ Q:J+J>A  s I=A-J-J*A-(J*J)/J/2 i I>0,'(I#1) s B=A+I,C=B+J,N1=A,N2=B x XGCD s N1=GCD,N2=C x:N1>1 XGCD i GCD=1 w "(",A,",",J,",",I,") ",A,"x",B,"x",C,! r X i $l(X) s:X'<1 A=X-11,X="" w ! q ;list PERTs

It’s still shy of the “holy grail” of all generating algorithm, a simple polynomial expression, but is a substantial – N^(1/2) times, to be precise – improvement.

 

No progress to report on the “Find a closed formula giving the number of perfect right triangles M(A)” challenge from post #1.

 

Thanks, everybody, for all the great contributions to our exportation of the venerable Pythagorean formula :angel:

[TheBigDog]

Craig, I was lent a book today. "Recreations in the Theory of Numbers - the Queen of Mathematics Entertains" by Albert H Beiler. Chapter 14 - The Eternal Triangle - is dedicated to integral right triangles. Many insights to be found, including a formula that dates back... way back.

 

With legs X and Y and Hypotenuse Z...

 

X = m^2 - n^2

Y = 2mn

Z = m^2 + n^2

 

m and n can be any positive integers where m > n, and each combination generates an IRT. In the book, what we call PIRT he calls primitive. That formula does not find all IRTs. He corrects this by modifying the formula like so...

 

X = K(m^2 - n^2)

Y = K(2mn)

Z = K(m^2 + n^2)

 

Where K becomes a common factor of all three sides. In his example 9x12x15 cannot be derived from the first formula.

 

This is from the first 4 of the 30 pages dedicated to right triangles. Thought this might help.

 

Bill

[Pyrotex]

Craig, I was lent a book today. "Recreations in the Theory of Numbers - ...

X = m^2 - n^2

Y = 2mn

Z = m^2 + n^2

Excellent, Bill.

I have seen those formulas before, long ago. But I do not think they generate all PIRTs. I believe they generate only certain deltas. I wish I had time to work on this right now, but I don't. :eek2:

[CraigD]

Thanks, Bill – Beiler’s old book sound so cool, I just bought one for $15 at amazon. ;) (I am part of the reason my local public libraries are falling apart ;) )

… But I do not think [X=K(M^2-N^2), Y=K(2MN), Z=K(M^2+N^2)] they generate all PIRTs. I believe they generate only certain deltas …

I’ve played with the formula a bit (about 1,000,000 IRT/PIRTs), and haven’t found any IRT/PIRTs if fails to generate. With its help, I found a sloppy rounding bug in the code in posts #1 and 19, which I’ll fix ASAP!

 

It’s a little tricky to compare to algorithms like those in posts #1 and 19, because it doesn’t find IRTs “densely” – modified to generate only PIRTs, it generates 5535x8272x9953 after 1570 outputs, but doesn’t generate 443x98124x98125 until after 10011. The post #19 algorithm generates PIRTs in order of their smallest side (A) , generating 443x98124x98125 after 572, 5535x8272x9953 after 10002.

 

It appears that if you restrict the integers used in the Beiler’s old formula as follows:

K=1;

M and N have no factors in common (relatively prime);

M or N have a factor of 2,

It generates a subset of its “primitives” equal to the PIRTs, and generates them uniquely. Otherwise, it generates all of the IRTs, not uniquely. Actually making it into a IRT generating algorithm requires permuting K, M, and N using a Cartesian counting algorithm, and doesn’t seem worth doing, since it’s so easy to get it to generate the PIRTs.

 

We’re still no closer to the challenge in post #1, but appear to be having fun and giving our exercising our intuition. Thanks, everybody who’s contributed to or just read and enjoyed this thread – it’s much more fun – and more productive – to explore such things in company than alone. :rant:

[Pyrotex]

Thanks, Bill – Beiler’s old book sound so cool, I just bought one for $15 at amazon. ;) (I am part of the reason my local public libraries are falling apart ;) )I’ve played with the formula a bit (about 1,000,000 IRT/PIRTs), and haven’t found any IRT/PIRTs if fails to generate. ...

 

Yep. You are right on. And I found the half the reason for the strange choice of deltas:

 

z = m^2 + n^2

y = 2mn

 

delta = z-y = m^2 - 2mn + n^2

 

delta = (m - n)^2

 

now, you specified that one of them, say m, was even.

 

delta = (2p - n)^2

 

we are free to choose any p and any n integer as long as they are relatively prime. therefore, if n is an ODD integer, we get

 

deltaOdd = (odd integer)^2

 

if n is an EVEN integer, we get

 

deltaEven = (2p - 2q)^2 = 4(p - q)^2

=4 * (any integer)^2

 

This is off by a factor of 2??????

 

Anybody see a way out of this?

[CraigD]

delta = (m - n)^2

…

if n is an EVEN integer, we get

 

deltaEven = (2p - 2q)^2 = 4(p - q)^2

=4 * (any integer)^2

m and n must be relatively prime even when (m – n) is even, so you can’t substitute “2p” for “m” and “2q” for “n”

 

I’d an idea that starting with

Delta = (m + n)^2 - 4mn

might be useful, but got stuck a few steps later

 

I don’t have time to work on it right now. but will get back to it when I can.

 

I have a hunch this may be more difficult than it seems.

 

Happy figuring ;)

[CraigD]

… is off by a factor of 2??????

 

Anybody see a way out of this?

… I have a hunch this may be more difficult than it seems.

My initial direction and subsequent hunch were wrong. This isn’t a hard problem after all.

 

Inspect a few N,P pairs that satisfy being relatively prime and one of them having a factor of 2.

M,N    X,Y,Z
2,1    3,4,5
3,2    5,12,13
4,1    15,8,17
4,3    7,24,25
5,2    21,20,29
5,4    9,40,41
…

Notice that X,Y,Z are not always ordered from least to greatest. Sometimes Y < X.

 

For the case where Y > X, Pyrotex’s derivation,

z = m^2 + n^2

y = 2mn

 

delta = z-y = m^2 - 2mn + n^2

 

delta = (m - n)^2

 

now, you specified that one of them, say m, was even.

 

delta = (2p - n)^2

 

we are free to choose any p and any n integer as long as they are relatively prime. therefore, if n is an ODD integer, we get

 

deltaOdd = (odd integer)^2

applies, giving the formula for deltaOdd. For the case where X > Y,

 

delta = z – x = (m^2 + n^2) – (m^2 – n^2) = 2n^2

 

Since only one of m and n must be even, and we are free to chose any m and p that are relatively prime, n can be ANY integer, so

 

deltaEven = 2n^2 = 2(even integer)^2

 

Thus the strange pair of formulae for PIRT deltas is explained. (QED ;) ;) :evil: )

[Pyrotex]

...This isn’t a hard problem after all....Thus the strange pair of formulae for PIRT deltas is explained. (QED :) :) :) )

Well done! Shiny!

:doh: :) :) :)

[Pyrotex]

For a thorough analysis of Primitive Pythagorean Triplets (which we have been calling PIRTs), see

http://en.wikipedia.org/wiki/Pythagorean_triple

This link contains OUR scatter plot of PIRTs!

And the formula(s) for calculating all PIRTs:

This shows that there are infinitely many primitive Pythagorean triples. This formula was given by Euclid (c. 300 B.C.) in his book Elements and is referred to as Euclid's formula.

The link gives many other fascinating relationships among the sides of a PIRT.

Enjoy!!!!!!!