Complexity of Pythagorean triples

Question

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$.

In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit iff $b>a$.

---

Let $\mathcal P$ be the set of all legit Pythagorean triples.

We define a lexicographic order $\prec$ on $\mathcal P$, such that $$\langle a_1,b_1,c_1\rangle\prec\langle a_2,b_2,c_2\rangle\iff (a_1< a_2)\vee ((a_1=a_2)\wedge(b_1<b_2)$$

Let $$L_\mathrm{PT}=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P\text{ w.r.t.}\prec\}$$

What can we say about the complexity of $L_\mathrm{PT}$?

We say that a triple $\langle a,b,c\rangle$ is minimal if $gcd(a,b,c)=1$. Let $\mathcal P_\mathrm{M}$ be the set of all legit, minimal triples.

We define $$L_\mathrm{PT}'=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P_\mathrm{M}\text{ w.r.t.}\prec\}$$

What can we say about the complexity of $L'_\mathrm{PT}$?

Answer 1

This is not a full answer, but I think it is very useful.

Euclid's formula generates all primitive triples in a fairly linear fashion. Using all integers $m, n$ with $m > n$, $m, n$ coprime and $m-n$ is odd, all primitive triples can be generated as

$$a=m^2-n^2, b=2mn, c=m^2 + n^2$$

I don't have any knowledge on complexity, but hopefully this will help