# Length of Shortest Path in a Generated Binary Tree

Let's say I have a binary tree of $2$-tuples of positive integers starting with $(1,1)$. The left-child of any element $(A,B)$ is $(A,A+B)$, and the right-child of any element is $(A+B,A)$. Hence, the parent of $(A,B)$ is $(\min(A,B), |A-B|)$.

Is there an expression for the length of the shortest path from $(A,B)$ to $(1,1)$, in terms of just $A$ and $B$? There is an obvious recursive algorithm, but I am more interested in a closed-form expression.

-

The function taking node $(A,B)$ to its parent node $(\min(A,B), |A-B|)$ is exactly Euclid's algorithm for calculating the greatest common divisor of $A$ and $B$. If $\gcd(A,B)>1$, then the root node $(1,1)$ will never be reached... instead you will reach $(x,x)$ for $x>1$... so the only pairs generated by your tree are those where $A$ and $B$ are relatively prime. For these pairs, there does not seem to be a closed form for the number of steps required. However, because of the connection between Euclid's algorithm and the continued-fraction representation, it seems likely that there is an expression that relates the depth of $(A,B)$ in your tree (when $A$ and $B$ are coprime) to the continued fraction for $A/B$.
This is in fact the case. Consider two examples. The depth of $(17, 103)$ in the tree is $23$ (taking the root to be at depth $1$), and the continued fraction for $103/17$ is $[6;17]$. The depth of $(17,105)$ in the tree is $14$, and the continued fraction for $105/17$ is $[6;5,1,1,1]$. It is clear that the depth of $(A,B)$ in the tree is just the sum of quotients of the continued fraction for $A/B$.