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

Question

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.

Answer 1

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

Answer 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]

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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