29
2
(related)
A Pythagorean Triple is a list (a, b, c)
that satisfies the equation a2 + b2 = c2.
A Primitive Pythagorean Triple (PPT) is one where a
, b
, and c
are all coprime (i.e., the only common divisor between the three elements is 1
). For example, the (3, 4, 5)
right triangle is a famous Primitive Pythagorean Triple.
The Challenge
- Given input
n
, output then
th PPT. Or, - Given input
n
, output the firstn
PPTs.
There are multiple ways to order these PPTs to form a well-ordered list, to determine which is the n
th. You can choose any ordering you want, so long as you can prove (informally is fine) that your algorithm can generate every possible unique PPT. For example, your code should not output both (3,4,5)
and (4,3,5)
since those are duplicates of the same triple -- one or the other, please.
Similarly, whether your code is zero- or one-indexed is fine, so long as you state which you're using.
Examples
For the examples below, I'm using one-indexing, outputting the n
th PPT, and ordering by smallest c
, then smallest a
, then smallest b
.
n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)
Rules
- The input and output can be given in any convenient format.
- In your submission, please state how your entries are ordered, and whether your entries are 0-indexed or 1-indexed.
- Your chosen ordering cannot create duplicates.
- Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
- If possible, please include a link to an online testing environment so other people can try out your code!
- Standard loopholes are forbidden.
- This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.
Related – miles – 2017-07-25T13:29:07.227
2A103606. – miles – 2017-07-25T13:38:42.380
What is the highest input we have to support? Can we assume that it fits the capabilities of our language of choice? – Mr. Xcoder – 2017-07-25T13:40:27.440
1
@Mr.Xcoder Yes; that's a standard safe assumption, unless you're using that to exploit a loophole (e.g., the language only supports 1-bit numbers) to make the problem trivial.
– AdmBorkBork – 2017-07-25T13:43:02.680Should triples only occur in one order (i.e.
a < b
ora > b
)? – PurkkaKoodari – 2017-07-25T13:43:32.547@Pietu1998 They should be unique. I'll add some clarifying words. – AdmBorkBork – 2017-07-25T13:44:46.360
Is it necessary to output
a,b,c
, or doesa,b
suffice? – Luis Mendo – 2017-07-25T14:00:44.530@LuisMendo The full
a,b,c
, please, as that is the common nomenclature. – AdmBorkBork – 2017-07-25T14:03:28.980I'd be delighted to see a Python solution to this challenge... – Mr. Xcoder – 2017-07-26T06:05:51.243
should really a,b,c be coprime? a and b is not enough? – edc65 – 2017-07-26T08:54:59.527
2
I found the answer to my question: a and b must be coprime and this is enough https://proofwiki.org/wiki/Elements_of_Primitive_Pythagorean_Triple_are_Pairwise_Coprime
– edc65 – 2017-07-26T09:25:28.607