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 fractiona(n)/a(n+1) = x
by1/(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.