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.

• Darren Stone: 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?
• Joe Z.: A function is sufficient. I'll make that clearer in the problem description.
• Joe Z.: It's a bit late for me to be thinking about it; I'll probably try to clarify it tomorrow.
• Peter Taylor: 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: 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).

Answer 1

Python 3, (削除) 98 (削除ここまで) 83 bytes

f=lambda a,b,n=1,d=2:a>b and f(a-b,b,n*2+1,d*2)or a<b and f(a,b-a,n*2-1,d*2)or(n,d)

Try it online!

Explanation: The sequence of turns starting from 1 down to the given fraction in the Stern-Brocot tree is identical to the sequence of turns starting from the given fraction going to 1 in the Calkin-Wilf tree. This makes it much simpler to get the sequence.

Improvement given by Bubbler. Original solution here.

• rydwolf: Welcome to Code Golf, and nice answer!
• Bubbler: Quick suggestions: You don't need parens in while and if clauses, and a!=b is equivalent to a-b being nonzero (and hence truthy). Also, a,n=a-b,n+1 can be shortened to a-=b;n+=1. This gives 91 bytes.
• Bubbler: A recursive lambda also works here. Check out Tips for golfing in Python for more tips like this.

Answer 2

GolfScript ((削除) 49 48 (削除ここまで) 46 chars)

{0\@{}{@2*22ドル$>!+@@{{\}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 3

(削除) 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.

• Howard: 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.
• Peter Taylor: @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.
• Howard: Try c=a<b ? with an extra space after b. Otherwise the questionmark is treated as part of the b.

Answer 4

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 5

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 6

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

Answer 7

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 8

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 9

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 10

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