Output the nth rational number according to the Stern-Brocot sequence

Haskell, 78 77 65 58 bytes

Shamelessly stealing the optimized approach gives us:

(s#t)0=show s++'/':show t
(s#t)n=t#(s+t-2*mod s t)$n-1
1#1

Thanks to @nimi for golfing a few bytes using an infix function!

(Still) uses 0-based indexing.


The old approach:

s=(!!)(1:1:f 0)
f n=s n+s(n+1):s(n+1):(f$n+1)
r n=show(s n)++'/':(show.s$n+1)

Damn the output format... And indexing operators. EDIT: And precedence.

Fun fact: if heterogenous lists were a thing, the last line could be:

r n=show>>=[s!!n,'/',s!!(n+1)]

CJam (20 bytes)

1_{_@_2$%2*-+}ri*'/\

Online demo. Note that this is 0-indexed. To make it 1-indexed, replace the initial 1_ by T1.

Dissection

This uses the characterisation due to Moshe Newman that

the fraction a(n+1)/a(n+2) can be generated from the previous fraction a(n)/a(n+1) = x by 1/(2*floor(x) + 1 - x)

If x = s/t then we get

  1 / (2 * floor(s/t) + 1 - s/t)
= t / (2 * t * floor(s/t) + t - s)
= t / (2 * (s - s%t) + t - s)
= t / (s + t - 2 * (s % t))

Now, if we assume that s and t are coprime then

  gcd(t, s + t - 2 * (s % t))
= gcd(t, s - 2 * (s % t))
= gcd(t, -(s % t))
= 1

So a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1)) works perfectly.

1_           e# s=1, t=1
{            e# Loop...
  _@_2$%2*-+ e#   s, t = t, s + t - 2 * (s % t)
}
ri*          e# ...n times
'/\          e# Separate s and t with a /

Jelly, 16 bytes

L‘Hị⁸Sṭ
1Ç¡ṫ-j”/

Try it online! or verify all test cases.

How it works

1Ç¡ṫ-j”/  Main link. Argument: n

1         Set the return value to 1.
 Ç¡       Apply the helper link n times.
   ṫ-     Tail -1; extract the last two items.
     j”/  Join, separating by a slash.


L‘Hị⁸Sṭ   Helper link. Argument: A (array)

L         Get the length of A.
 ‘        Add 1 to compute the next index.
  H       Halve.
   ị⁸     Retrieve the item(s) of A at those indices.
          If the index in non-integer, ị floors and ceils the index, then retrieves
          the items at both indices.
    S     Compute the sum of the retrieved item(s).
     ṭ    Tack; append the result to A.