Talk:Pythagorean triples

Confirmation of coprime

So perimeter is really easy. Coprime isn't something that people outside of math talk about much. I had to look it up on Wikipedia to figure it out, but I'm still not quite sure. It's defined nicely there for two numbers, but we are dealing with three here. Are a, b, and c coprime if gcd(a, b) = gcd(b, c) = gcd(a, c) = 1? Do I need the third gcd evaluation? --Mwn3d 15:28, 28 June 2011 (UTC)

Since a^2 + b^2 == c^2, if any two of them are coprime, the third is also coprime to both, so there's no difference how you interpret "coprime" in this situation. --Ledrug 15:50, 28 June 2011 (UTC)

I see what you did there. So, in general, you need all three gcd's, but in this case (because of the relationship between a, b, and c) you only need two. --Mwn3d 16:16, 28 June 2011 (UTC)

Slight correction: you only need one. --Ledrug 16:18, 28 June 2011 (UTC)

For reference

The correct results:<lang> 10 0 0

         100 17 7
       1,000 325 70
      10,000 4858 703
     100,000 64741 7026
   1,000,000 808950 70229
  10,000,000 9706567 702309
 100,000,000 113236940 7023027

1,000,000,000 1294080089 70230484 </lang> --Ledrug 18:27, 28 June 2011 (UTC)

Hmmm... I get 324 and 4857 for perimeters of 1000 and 10000 respectively. I see that the Python solution also gets 324 for a perimeter of 1000. Am I missing something?--Tikkanz 23:59, 28 June 2011 (UTC)

I got 325 for 1000 using Java. Here's the full list: http://pastebin.com/HK74uBCz --Mwn3d 00:49, 29 June 2011 (UTC)

Good, beat me to it. I was wondering if I should post the list here, guess not :) --Ledrug 00:52, 29 June 2011 (UTC)

I'm running 10K now. Even if it finishes before I get bored I don't think I'll put up the full list. It seems like too much. I'll add the count here in any case. --Mwn3d 00:54, 29 June 2011 (UTC)

It finished immediately after I clicked "submit"... I got 4858 triples and 703 primitives. --Mwn3d 00:55, 29 June 2011 (UTC)

Thanks, was a simple case of using < rather than <=. The Python solution should probably be corrected too.--Tikkanz 20:35, 29 June 2011 (UTC)

Ok the goal of the extra, as I stated in task, is not to brute force them. 100k will seriously get on your nerves. Instead of searching all possible triples, look at the generation section in the WP article, and device a good algorithm to create them: it's a world of difference. I'll post a solution if everyone gives up, but I really want to have a task where people are required to think a lot. --Ledrug 01:16, 29 June 2011 (UTC)

Thinking is for Project Euler! Maybe I'll try soon anyway. --Mwn3d 01:40, 29 June 2011 (UTC)

Heh funny you mentioned PE, this task is very similar in spirit, if not a down right copycat (it probably is, since there are many puzzles on PE that deal with right triangles). --Ledrug 01:48, 29 June 2011 (UTC)

J solution

The J code speed sounds pretty good, now only if I can tell what the hell is going on in that code... care to explain, Rdm? --Ledrug 03:55, 29 June 2011 (UTC)

Ok... I'm using Euclid's formula and generating primitive triples. In other words, for all positive integers m and n where $m\leq {\sqrt {p}}erimeter$ and m > n and m+n is odd, I find the triple a,b,c = ((m^2)-(n^2)),(2*m*n),((m^2)+(n^2)), and discard those where the sum is greater than the perimeter. I then find all multiples of each primitive triple where the multiple fits within the perimeter. I'm also sorting the result. I'm also going through some extra wasted motion (for example, I am currently discarding duplicates though I can't find any cases where that is necessary). --Rdm 10:52, 29 June 2011 (UTC)

Clever. Thanks for the answer. --Ledrug 21:16, 29 June 2011 (UTC)

Also seen at

FYI - Pythagorean triples are aslo part of List_comprehensions and snuck into Amb --Dgamey 12:39, 29 June 2011 (UTC)

I think it's OK to have this task because it allows for "whatever you want" solutions. If there are examples in other tasks that do something really close to this, they can be copied here, modified for this task's requirements, and annotated. -Mwn3d 13:02, 29 June 2011 (UTC)

Actually I don't think this task has much to do with list comprehensions at all. It just happens that that task uses Pythagorean triples as examples, while this task cannot be efficiently solved with list comprehension -- or show me how. --Ledrug 21:35, 29 June 2011 (UTC)

Algorithm and performance: simple analysis

Since this task was made to show importance of a good algorithm, it would be helpful to make the difference clear. Here are my understanding of different methods:

0. Task does not call for storing the triples, so space requirement is what you need to find each, meaning stack space and temp storage depending on how your method and language deal with them.

1. Brute force search of all a, b, c values. Most naive would be checking all three in the space of 1 to perimeter, resulting a $O(n^{3})$, but that's low even for a brute force: given a and b, only one value of c needs to be chcked. This is $O(n^{2})$, plus the complexity of testing square number and gcd; gcd is generally about $O({\rm {log}}n$; square testing can be $O({\rm {log}}n)$ if you have prime numbers pre-generated, are using sqrt function, or pre-generated all squares and stored in a hash. Besides these, there's no extra space requirement.

2. Generating triples with Euclid's method; this involves how you choose $u,v$ values. This is difficult to categorize. If you are picking those pairs to only generate primitive triples, creating a pair of coprime numbers are at least $O(n{\rm {log}}n)$ I think, though once a pair is there, no additional work is needed. If you also generate non-primitive triples, it may be much slower. If using loops, there's no extra space required.

3. Generating triples with the parent-child relationship. Each iteration increases perimiter of current triple by about 2, so recursion will run $O({\rm {log}}n)$ deep, that's also the space requirement (stack space); each recursion produces 3 triples, so running time is 3 to the power of depth, which is $O(n)$. Non-primitives come with no extra cost. For this particular task, it may be the most efficient method speed-wise. --Ledrug 23:56, 29 June 2011 (UTC)

Ready to graduate?

I think this task is pretty stable and clear. It seems like it's ready to come out of draft. Objections? --Mwn3d 19:53, 4 August 2011 (UTC)

Strengthening the condition

I see that there's a condition that $a\leq b\leq c$, but I believe that (with the exception of the case where all values are zero) this can be strengthened to $a<b<c$, because if ${\mathit {a}}=b$ then it means that either ${\mathit {c}}$ is zero (in which case they can't be coprime, and aren't positive integers anyway) or its square is exactly twice the square of ${\mathit {a}}$ (impossible because the square root of 2 is irrational).

Maybe that will help someone. :-) –Donal Fellows 10:23, 11 August 2011 (UTC)

*shrug* I changed it. Though I doubt it will help anyone: even if one is using brute furce, the right triangle condition provides a much stronger constraint anyway. --Ledrug 21:22, 11 August 2011 (UTC)

Math tags broken?

I see literal <math></math> tags everywhere...
Is this a bug introduced by the server switch perhaps?

Looks like it. Already reported to site owner. –Donal Fellows 13:58, 14 December 2011 (UTC)