2
$\begingroup$

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.

1 Answers 1

2

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$.

  • 0
    Ah, i see it now. The reason this happens is obvious if you think about what happens at each step of the Euclidean algorithm. It also seems to be related to this sequence, which is the sum of quotients when the Euclidean algorithm acts on two integers: http://oeis.org/A049834/internal2012-11-23