# Find a fraction's position in the Stern-Brocot tree

The Stern-Brocot tree is a binary tree of fractions where each fraction is acquired by adding the numerators and denominators of the two fractions neighbouring it in the levels above.

It is generated by starting with 0/1 and 1/0 as "endpoint fractions", and from there, iterating by placing one fraction between each consecutive pair of fractions by adding the numerators and denominators of those fractions together, like so:

0.  0/1                                                             1/0
1.  0/1                             1/1                             1/0
2.  0/1             1/2             1/1             2/1             1/0
3.  0/1     1/3     1/2     2/3     1/1     3/2     2/1     3/1     1/0
4.  0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0


In each iteration of the Stern-Brocot tree (the nth iteration), there are 2^n + 1 elements in the sequence, to which we can ascribe a fraction from 0/2^n to 2^n/2^n. Each new iteration simply inserts one fraction "halfway" between each pair of consecutive fractions.

This makes the Stern-Brocot tree a one-to-one mapping between the positive rational numbers and the binary fractions between 0 and 1, thereby also serving as a proof that the two sets have the same cardinality.

Your task is to write a program or function that, given the numerator and denominator of a positive rational number in lowest terms, determines the binary fraction that corresponds to that fraction's position in the Stern-Brocot tree.

Examples of inputs and outputs are provided below:

2/3 -> 3/8   (4th number in iteration 3)
4/7 -> 9/32  (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2   (middle number in the first iteration)


Inputs you don't need to support, but are included for reference:

0/1 -> 0/1   (0/1 is considered the left number)
1/0 -> 1/1   (1/0 is considered the rightmost number)


The shortest program in any language to achieve this goal wins.

• Are there any input/output requirements? e.g. Is just a function sufficient as in your reference solution, or does it need to be a stand-alone program? Does fraction output format matter? – Darren Stone Dec 15 '13 at 10:26
• A function is sufficient. I'll make that clearer in the problem description. – Joe Z. Dec 15 '13 at 11:25
• It's a bit late for me to be thinking about it; I'll probably try to clarify it tomorrow. – Joe Z. Dec 15 '13 at 13:01
• Ok, I think the bijection you have in mind is to assign to each depth in the tree a constant denominator 2^(depth+1) and numerators 1, 3, 5, 7, ... from the left. – Peter Taylor Dec 15 '13 at 23:15
• An alternative way of constructing it is to first number the nodes of the tree in breadth-first order starting at 1 (i.e. 1/1 => 1, 1/2 => 2, 2/1 => 3, 1/3 => 4, etc.). If the number so generated for a node is n, then 2^lg n (binary log) is the highest bit set in n, and the desired binary fraction is (2*(n - 2^lg n) + 1) / 2^(lg n + 1). (Anyone attempting an assembler solution in an instruction set with a get-highest-set-bit will probably want to use this approach). – Peter Taylor Dec 16 '13 at 13:55

## GolfScript (49 48 46 chars)

{0\@{}{@2*2$2$>!+@@{{\}3$)*}:j~1$-j}/\)\,?}:f;


or

{0:x;\{}{.2$<!2x*+:x){\}*1$-{\}x)*}/x@)@,?}:g;


Both are functions which take the numerator and denominator on the stack and leave the numerator and denominator on the stack. Online demo.

The core idea is expressed in pseudocode in Concrete Mathematics section 4.5 (p122 in my edition):

while m != n do
if m < n then (output(L); n := n - m)
else (output(R); m := m - n)


If the string of Ls and Rs is interpreted as a binary value with L=0 and R=1 then twice that value plus one is the numerator, and the denominator is one bit longer.

As a point of interest to Golfscripters, this is one of those rare occasions when I've found unfold useful. (Ok, I only use it as a loop counter, but that's better than nothing).

# Mathematica, 130 114 111 chars

f=#~g~0&;0~g~q_=q;p_~g~q_:=g[#,(Sign[p-#]+q)/2]&@FromContinuedFraction[ContinuedFraction@p/.{x___,n_}:>{x,n-1}]


### Example:

f[2/3]


3/8

f[4/7]


9/32

f[1]


1/2

## Ruby, 132 125

Rubied & golfed the reference solution from @JoeZ.

def t(n,d)u=k=0;v,j,f,g,b=[1,]*5;c=2
while(z=(f*d).<=>(g*n))!=0;z>0?(j,k=f,g):(u,v=f,g);b=b*2-z;f,g=u+j,v+k;c*=2;end
[b,c]end


Usage examples:

>> t(2,3)
=> [3, 8]
>> t(4,7)
=> [9, 32]
>> t(1,1)
=> [1, 2]


## Ruby (69 chars) CoffeeScript (59 chars)

This is a function which takes numerator and denominator as arguments and returns an array containing the numerator and denominator after the bijection.

g=(a,b,x=0,y=1)->c=a>=b;a&&g(a-b*c,b-a*!c,2*x+c,2*y)||[x,y]


Online demo

It uses the same approach as my GolfScript solution above, but is much more readable because I can use 4 variables without having to worry about boxing and unboxing into an array. I chose CoffeeScript because it doesn't prefix variables with $ (20 chars saved over e.g. PHP), has short function definition syntax which allows default parameter values (so there's no need to wrap f(a,b,x,y) in a function g(a,b) = f(a,b,0,1)), and lets me use Booleans as integers in expressions with useful values. For those who don't know it, CoffeeScript doesn't have the standard C-style ternary operator (C?P:Q), but I'm able to substitute C&&P||Q here because P will never be falsy. An arguably more elegant, but inarguably less short, alternative is to replace the repeated subtraction with division and modulo: f=(a,b,x=0,y=1,p=0)->a&&f(b%a,a,(x+p<<b/a)-p,y<<b/a,1-p)||[x+p,y]  (65 chars; online demo). Writing it this way exposes the relationship with Euclid's algorithm. • You don't need the parentheses around a<b which saves you one char. Inlining c gives another two. You may also consider the syntax f=->a,b,x=0,y=1{...} for even shorter definition. – Howard Dec 16 '13 at 14:03 • @Howard, I don't know which version of Ruby you're using, but on IDEOne I get a syntax error if I try removing those parentheses or using that function syntax. – Peter Taylor Dec 16 '13 at 14:11 • Try c=a<b ? with an extra space after b. Otherwise the questionmark is treated as part of the b. – Howard Dec 16 '13 at 14:40 # Python - 531 An ungolfed solution in Python, to serve as a last-place reference solution: def sbtree(n, d): ufrac = [0, 1] lfrac = [1, 0] frac = [1, 1] bfrac = [1, 2] while(frac[0] * d != frac[1] * n): if(frac[0] * d > frac[1] * n): # push it towards lfrac lfrac[0] = frac[0] lfrac[1] = frac[1] bfrac[0] = bfrac[0] * 2 - 1 elif(frac[0] * d < frac[1] * n): # push it towards ufrac ufrac[0] = frac[0] ufrac[1] = frac[1] bfrac[0] = bfrac[0] * 2 + 1 frac[0] = ufrac[0] + lfrac[0] frac[1] = ufrac[1] + lfrac[1] bfrac[1] *= 2 return bfrac  It simply does a binary search between fractions, taking advantage of the fact that the mediant of any two fractions will always between the values of those two fractions. ### GolfScript, 54 characters '/'/n*~][2,.-1%]{[{.~3$~@+@@+[\]\}*].2$?0<}do.@?'/'@,(  Input must be given on STDIN in the form specified in the task. You may try the code online. > 4/7 9/32 > 9/7 35/64 > 5/1 31/32  # Mathematica 138 Not as streamlined as alephalpha's procedure, but it was the best I've been able to produce so far. q_~r~k_:=Nest[#+Sign@k/(2Denominator@# )&,q,Abs@k] g@d_:= Module[{l=ContinuedFraction@d,p=-1}, l[[-1]]-=1; (p=-p;# p)&/@l] h[q_]:=Fold[r,1/2,g@q]  Testing h[2/3] h[4/7] h[1]  3/8 9/32 1/2 # JavaScript 186 f=(p1,q1,p2,q2)=>{if(p1*q2+1==p2*q1){return{p:p1+p2,q:q1+q2}}let p,q,pl=0,ql=1,ph=1,qh=0;for(;;){p=pl+ph;q=ql+qh;if(p*q1<=q*p1){pl=p;ql=q}else if(p2*q<=q2*p){ph=p;qh=q}else return{p,q}}}  could be less, but I like readable golf # Haskell, 125 bytes n((a,b):(c,d):r)=(a,b):(a+c,b+d):n((c,d):r) n a=a z=zip[0..] t x=[(j,2^i)|(i,r)<-z$iterate n[(0,1),(1,0)],(j,y)<-z r,x==y]!!0


Try it online!

Input and output in the form of a pair (n,d).

Brief Explanation:

n constructs the next row from the previous one by looking at each pair of fractions and inserting the new one between the first and the recursion (which will put the second fraction right there). The base case is very simple since it's basically just the identity function. The t function iterates that function indefinitely based off the initial state with just the two boundary fractions. t then indexes each row (i) and each item in the row (j) and looks for the first fraction that matches what we're looking for. When it finds it yields j as the numerator and 2^i as the denominator.