# 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$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9301096796989441, "perplexity": 71.68392881339933}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-48/segments/1448398445142.9/warc/CC-MAIN-20151124205405-00329-ip-10-71-132-137.ec2.internal.warc.gz"}