Looking for the best way to find Pythagorean triples where $B-A=\pm1$.

Question

Pythagorean triples where $A-B=\pm1$ are some of the rarest; the $19^{th}$ has terms $A,B,C$ in the quadrillions. I found a formula in a book, "Pythagorean Triangles" that generates them in sequence beginning with a seed triple $T_1=(3,4,5)$: $A=3A+2C+1\quad B=3A+2C+2\quad C=4A+3C+2$ will generate $T_2=(20,21,29)\quad T_3=(119,120,169)\quad T_4=(697,696,985)$ and so on. Nineteen iterations gives you the first $19$ triples and that is great but I developed a formula which uses less computation until you get to the $n^{th}$ triple you want to view. It generates the parameters $(m,n)$ to feed Euclid's formula:$$A=m^2-n^2\quad B=2mn\quad C=m^2+n^2$$

The formula is $\quad m_{x+1}=2m_x+n_x\quad n_{x+1}=m_x\quad $ and generates the following pairs with a seed: $P_0=(1,0)$. $$P_1=(2,1)\quad P_2=(5,2)\quad P_3=(12,5)\quad P_4=(29,12)\quad P_5=(70,29)\quad P_6=(169,70)\quad ...$$

I would like to be able to generate the $6^{th}$ or the $1000^{th}$ pair directly without generating $1$-thru-$5$ or $1$-thru-$999$ to get there but I haven't been able to figure out any way to generate an individual pair directly. I have tried $2=2^1, 5=2^2+2^1, 12=2^3+2^2, hmm, 29=2^4+2^3+2^2+2^1+2^0 $ and other things like factors of $2,5,12,29...$ and I'm out of ideas.

Is it possible to generate an $x^{th}$ member pair using just $x$ as an input number or, by the nature of this sequence, is it required to generate all of them in order until I get to the desired pair?

Someone said my formula does not work but here it is working in a spreadsheet.

Answer 1

The computation of the Pythagorean triples of the form $T_n=(a_n,a_n+1,c_n)$ is equivalent to the computation of some convergents of the continued fraction of $\sqrt{2}$: in particular $$ [1;\underbrace{2,2,\ldots,2,2}_{2n\text{ times}}]=\frac{2a_n+1}{c_n} $$ where $$ c_n = \frac{(1+\sqrt{2})^{2n+1}-(1-\sqrt{2})^{2n+1}}{2\sqrt{2}},\qquad 2a_n+1 =\frac{(1+\sqrt{2})^{2n+1}+(1-\sqrt{2})^{2n+1}}{2}=d_n $$ both fulfill the recurrence $\ell_{n+2}=6\ell_{n+1}-\ell_n$. They can be expressed in terms of $D_n$ and $D_{n+1}$, where $$ D_n = (3+2\sqrt{2})^n+(3-2\sqrt{2})^n =\sigma^n+{\bar{\sigma}}^n$$ is the trace of the $n$-th power of a $2\times 2$ matrix. This sequence fulfills

$$ D_{2n} = D_n^2-2,\qquad D_{2n+1}=D_n D_{n+1}-6 \tag{R}$$ so the couple $(D_n,D_{n+1})$ can be computed by a repeat-squaring algorithm. A concrete example will hopefully clarify how. Let us assume to want to compute $D_{23}$ and $D_{24}$. The binary representation of $23$ is $10111_2$, so we compute the couples $(D_m,D_{m+1})$ for $m=1_2,10_2,101_2,1011_2$ and finally $10111_2$ via $(R)$. $$ (D_1,D_2)=(6,34) $$ $$ (D_2,D_3)= (34,198)$$ $$ (D_5,D_6)=(6726,39202) $$ $$ (D_{11},D_{12})=(263672646,15367968024) $$ $$ (D_{23},D_{24})=(405211279147678086,2361744410637427202)$$ This gives us $c_{23}$ and $d_{23}$, thus $T_{23}$, with no more than $3\log_2(23)$ multiplications.

Answer 2

Edited answer...

which starts with a comment.

The title Looking for the best way to find Pythagorean triples where $B−A=\pm1$ is possibly misleading for the actual question, which after many comments can be extracted only from the fact that the initial answer for the $(A,C)$ recursion (remained in the sequel) is not the wanted answer. Please always make clear in the OP which is the question (without alternatives, best stated as question, not as a wish).

The OP gives two ways to construct Pythagorean triples, one is "from a book" and constructs triples $T_x=(A_x,B_x,C_x)$ recursively, the other one comes from a formula, it constructs intermediate pairs $P_x=(m_x,n_x)$ given by an other recursion, that may be used to reconstruct $(A_x,B_x,C_x)$. As i extract the information from the comments, we need only the $P_x$ (despite of the title, and the initial digression / divagation on triples). OK, this is even simpler.

---

We have the linear recursion formula for the pair written as column vector $$ \begin{aligned} \begin{bmatrix} m_{x+1}\\ n_{x+1} \end{bmatrix} &= \begin{bmatrix} 2&1\\1&0 \end{bmatrix} \begin{bmatrix} m_{x}\\ n_{x} \end{bmatrix} \\ &= \underbrace{ \begin{bmatrix} 1+\sqrt 2&1-\sqrt 2\\1&1 \end{bmatrix}}_C \underbrace{ \begin{bmatrix} 1+\sqrt 2&\\&1-\sqrt 2 \end{bmatrix}}_D \underbrace{ \frac 1{2\sqrt 2} \begin{bmatrix} 1 &\sqrt 2-1\\-1&\sqrt 2+1 \end{bmatrix}}_{C^{-1}} \begin{bmatrix} m_{x}\\ n_{x} \end{bmatrix} \ , \end{aligned} $$ with a diagonal matrix $D$ above. The powers of $\begin{bmatrix}2&1\\1&0\end{bmatrix}$ are not immediate, but the powers of $D$ are. We get directly for your pairs formula the explicit version with proof: $$ \begin{aligned} \begin{bmatrix} m_x\\n_x \end{bmatrix} &= (CDC^{-1})^x\begin{bmatrix}m_0\\n_0\end{bmatrix} = CD^xC^{-1}\begin{bmatrix}1\\0\end{bmatrix} \\[2mm] &= \frac 1{2\sqrt 2} \begin{bmatrix} 1+\sqrt 2&1-\sqrt 2\\1&1 \end{bmatrix} \begin{bmatrix} (1+\sqrt 2)^x&\\&(1-\sqrt 2)^x \end{bmatrix} \begin{bmatrix} 1 &\sqrt 2-1\\-1&\sqrt 2+1 \end{bmatrix} \begin{bmatrix}1\\0 \end{bmatrix} \\[2mm] &= \frac 1{2\sqrt 2} \begin{bmatrix} (1+\sqrt 2)^{x+1} & (1-\sqrt 2)^{x+1}\\ (1+\sqrt 2)^{x } & (1-\sqrt 2)^{x } \end{bmatrix} \begin{bmatrix} 1 &\sqrt 2-1\\-1&\sqrt 2+1 \end{bmatrix} \begin{bmatrix}1\\0 \end{bmatrix} \\[2mm] &= \frac 1{2\sqrt 2} \begin{bmatrix} (1+\sqrt 2)^{x+1} - (1-\sqrt 2)^{x+1} & ? \\ (1+\sqrt 2)^{x } - (1-\sqrt 2)^{x } & ? \end{bmatrix} \begin{bmatrix}1\\0 \end{bmatrix} \\[2mm] &= \frac 1{2\sqrt 2} \begin{bmatrix} (1+\sqrt 2)^{x+1} - (1-\sqrt 2)^{x+1} \\ (1+\sqrt 2)^{x } - (1-\sqrt 2)^{x } \end{bmatrix} \ , \end{aligned} $$ which gives $\displaystyle n_x=\frac 1{2\sqrt 2}\Big(\ (1+\sqrt 2)^{x } - (1-\sqrt 2)^{x }\ \Big)$.

$\square$

In particular, for $x>0$ we can compute $n_x$ by rounding to an integer the number $\displaystyle n_x=\frac 1{2\sqrt 2} (1+\sqrt 2)^x$. For instance, for $x=7$ we obtain $168.99926035179\dots$ and after rounding we get $n_7=169$.

---

Older answer for the explicit form of the $(A,C)$ recursion:

You may try to write explicitly the recursion formula as passing from one pair $(A,C)$ to the next pair $(A',C')$ in the form: $$ \begin{aligned} \begin{bmatrix} A'\\C'\\1 \end{bmatrix} &= \underbrace{ \begin{bmatrix} 3&2&1\\4&3&2\\0&0&1 \end{bmatrix}}_{=:T} \begin{bmatrix} A\\C\\1 \end{bmatrix} \ , \\ &\qquad\text{ extracted from the mentioned passage} \\ A' &=3A+2C+1\ ,\\ C' &=4A+3C+2\ , \end{aligned} $$ thus introducing a matrix $T$. Its charactristic polynomial is $(x - 1) (x^2 - 6x + 1)$, so we have the following diagonalization over $\Bbb Q(a)$ with $a=\sqrt 2$. We expect a diagonal matrix with diagonal entries corresponding to the roots of the above characteristic polynomial, they are $1$ and $3\pm 2\sqrt 2$. Computer aided typing:

sage: K.<a> = QuadraticField(2)
sage: a^2
2
sage: T = matrix( K, 3,3, [3,2,1, 4,3,2, 0,0,1] )
sage: T
[3 2 1]
[4 3 2]
[0 0 1]
sage: D, change = T.jordan_form(transformation=True)
sage: D
[ 2*a + 3|       0|       0]
[--------+--------+--------]
[       0|       1|       0]
[--------+--------+--------]
[       0|       0|-2*a + 3]
sage: change
[ 1  1  1]
[ a  0 -a]
[ 0 -2  0]
sage: change * D * change^-1 == T
True

Later edit: Let us use, and type explicitly the obtained formula for $T$, and thus also for the powers of $T$. Below, $S$ is the base change matrix. $$ \begin{aligned} T &= \underbrace{ \begin{bmatrix} 1&1&1\\ a&0&-a\\ 0&-2&0 \end{bmatrix}}_S \begin{bmatrix} 3+2a&&\\ &1&\\ &&3-2a \end{bmatrix} \underbrace{ \frac 14 \begin{bmatrix} 2 & a & 1\\ 0&0&-2\\ 2&-a&1 \end{bmatrix}}_{S^{-1}} \\ T^n &= \frac 14 \begin{bmatrix} 1&1&1\\ a&0&-a\\ 0&-2&0 \end{bmatrix} \begin{bmatrix} (3+2a)^n&&\\ &1&\\ &&(3-2a)^n \end{bmatrix} \begin{bmatrix} 2 & a & 1\\ 0&0&-2\\ 2&-a&1 \end{bmatrix} \\[3mm] &\qquad\text{ Above }a=\sqrt 2\ . \\ &\qquad\text{ This gives an }\color{blue}{\text{explicit formula}:} \\[3mm] \color{blue}{ \begin{bmatrix} A_n\\ C_n\\ 1 \end{bmatrix}} &= T^n \begin{bmatrix} A_0\\ C_0\\ 1 \end{bmatrix} = T^n \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix} \\ &= \color{blue}{ \frac 14 \begin{bmatrix} 1&1&1\\ a&0&-a\\ 0&-2&0 \end{bmatrix} \begin{bmatrix} (3+2a)^n&&\\ &1&\\ &&(3-2a)^n \end{bmatrix} \begin{bmatrix} 2 & a & 1\\ 0&0&-2\\ 2&-a&1 \end{bmatrix} \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix}}\ . \end{aligned} $$

$\square$

---

Please stop reading here if computer experiments are not welcome. (I posted this since the shape of the OP also has similar collection of data. It is often for me a check, and in this case it may be helpful for some readers, too.)

---

Example of an explicit computation:

To compute -say- the $15$.th term (or so) we already have $D^{15}$, so compute with sage the product: $$ \frac 14 \begin{bmatrix} 1&1&1\\ a&0&-a\\ 0&-2&0 \end{bmatrix} \begin{bmatrix} (3+2a)^{15}&&\\ &1&\\ &&(3-2a)^{15} \end{bmatrix} \begin{bmatrix} 2 & a & 1\\ 0&0&-2\\ 2&-a&1 \end{bmatrix} \begin{bmatrix} 0\\1\\1 \end{bmatrix} \ , $$ and we get:

sage: Z = matrix(3, 1, [0,1,1])    # initial solution, A=0, C=1
sage: change * D^15 * change^-1 * Z
[183648021599]
[259717522849]
[           1]
sage: A15, C15 = 183648021599, 259717522849
sage: B15 = A15 + 1
sage: A15^2 + B15^2 == C15^2
True

This is the kind of direct computation needed. (The diagonal matrix $D$ has diagonal entries $1$, and $3\pm 2\sqrt 2$, so the only involved involved computation is the one of the powers of these diagonal entries.)