14
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ 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? \$\endgroup\$ Dec 15, 2013 at 10:26
  • \$\begingroup\$ A function is sufficient. I'll make that clearer in the problem description. \$\endgroup\$
    – Joe Z.
    Dec 15, 2013 at 11:25
  • \$\begingroup\$ It's a bit late for me to be thinking about it; I'll probably try to clarify it tomorrow. \$\endgroup\$
    – Joe Z.
    Dec 15, 2013 at 13:01
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Dec 15, 2013 at 23:15
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Dec 16, 2013 at 13:55

10 Answers 10

4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Feb 24, 2022 at 1:32
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Feb 24, 2022 at 2:27
  • 1
    \$\begingroup\$ A recursive lambda also works here. Check out Tips for golfing in Python for more tips like this. \$\endgroup\$
    – Bubbler
    Feb 24, 2022 at 2:32
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Howard
    Dec 16, 2013 at 14:03
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 16, 2013 at 14:11
  • \$\begingroup\$ Try c=a<b ? with an extra space after b. Otherwise the questionmark is treated as part of the b. \$\endgroup\$
    – Howard
    Dec 16, 2013 at 14:40
1
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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