Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
It is clear seems a bit of a stretch at this point. –  Brian M. Scott Nov 23 '12 at 14:57
    
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: oeis.org/A049834/internal –  Ryan Nov 23 '12 at 20:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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