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.
Best Answer
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.