5
$\begingroup$

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}$?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.