35
\$\begingroup\$

The Stern-Brocot sequence is a Fibonnaci-like sequence which can be constructed as follows:

  1. Initialise the sequence with s(1) = s(2) = 1
  2. Set counter n = 1
  3. Append s(n) + s(n+1) to the sequence
  4. Append s(n+1) to the sequence
  5. Increment n, return to step 3

This is equivalent to:

s(n) = \begin{cases} 1 & \textrm{if } n = 1 \ s(\frac n 2) & \textrm{if } n \textrm{ is even} \ s(\frac{n-1}2) + s(\frac{n+1}2) & \textrm{otherwise} \end{cases}

Amongst other properties, the Stern-Brocot sequence can be used to generate every possible positive rational number. Every rational number will be generated exactly once, and it will always appear in its simplest terms; for example, 1/3 is the 4th rational number in the sequence, but the equivalent numbers 2/6, 3/9 etc won't appear at all.

We can define the nth rational number as r(n) = s(n) / s(n+1), where s(n) is the nth Stern-Brocot number, as described above.

Your challenge is to write a program or function which will output the nth rational number generated using the Stern-Brocot sequence.

  • The algorithms described above are 1-indexed; if your entry is 0-indexed, please state in your answer
  • The algorithms described are for illustrative purposes only, the output can be derived in any way you like (other than hard-coding)
  • Input can be via STDIN, function parameters, or any other reasonable input mechanism
  • Ouptut can be to STDOUT, console, function return value, or any other reasonable output stream
  • Output must be as a string in the form a/b, where a and b are the relevant entries in the Stern-Brocot sequence. Evaluating the fraction before output is not permissable. For example, for input 12, output should be 2/5, not 0.4.
  • Standard loopholes are disallowed

This is , so shortest answer in bytes will win.

Test cases

The test cases here are 1-indexed.

n r(n) -- ------ 1 1/1 2 1/2 3 2/1 4 1/3 5 3/2 6 2/3 7 3/1 8 1/4 9 4/3 10 3/5 11 5/2 12 2/5 13 5/3 14 3/4 15 4/1 16 1/5 17 5/4 18 4/7 19 7/3 20 3/8 50 7/12 100 7/19 1000 11/39

OEIS entry: A002487
Excellent Numberphile video discussing the sequence: Infinite Fractions

Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ Can the output use Trues instead of 1s? \$\endgroup\$ Commented Aug 18, 2016 at 13:54
  • 1
    \$\begingroup\$ @Loovjo No, True/2 isn't a valid fraction (as far as I'm concerned). As an aside, True isn't always 1 - some languages use -1 instead to avoid potential mistakes when applying bitwise operators. [citation needed] \$\endgroup\$ Commented Aug 18, 2016 at 14:01
  • \$\begingroup\$ related \$\endgroup\$ Commented Aug 18, 2016 at 15:40
  • 2
    \$\begingroup\$ @Sok citation \$\endgroup\$ Commented Aug 18, 2016 at 17:13
  • 1
    \$\begingroup\$ @Sok but in Python, True is equivalent to 1 and True/2 would be 1/2. \$\endgroup\$ Commented Aug 20, 2016 at 8:06

29 Answers 29

Reset to default
13
\$\begingroup\$

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 /
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Love the methodology here, awesome answer! \$\endgroup\$ Commented Aug 19, 2016 at 8:00
  • \$\begingroup\$ If you scroll further down the OEIS entry you'll find that Mike Stay already submitted that formula. \$\endgroup\$ Commented Aug 21, 2016 at 11:04
11
\$\begingroup\$

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)]
Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ Using a guard to bind s!!n should be one byte shorter: f n|x<-s!!n=x:x+x+1:f$n+1 \$\endgroup\$ Commented Aug 18, 2016 at 12:53
  • \$\begingroup\$ @Laikoni s!!n+1 is not (s!!n)+1 but s!!(n+1) which is why I can't do that :/ \$\endgroup\$ Commented Aug 18, 2016 at 12:55
  • \$\begingroup\$ Indeed, that should have been obvious. Its just ... so many s!!n in there! \$\endgroup\$ Commented Aug 18, 2016 at 13:00
  • 1
    \$\begingroup\$ You can use ++'/':(show.s$n+1) in r to save a byte. \$\endgroup\$ Commented Aug 19, 2016 at 4:56
  • 1
    \$\begingroup\$ Switch to an an infix function: (s#t)0=show..., (s#t)n=t#(s+t-2*mod s t)$n-1, r=1#1. You can even omit r, i.e. the last line is just 1#1. \$\endgroup\$ Commented Aug 19, 2016 at 14:09
6
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 34 33 25 23 bytes

XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý

Explanation

XX‚ # push [1,1] ¹G } # input-1 times do  # bifurcate 2£ # take first 2 elements of reversed list DO¸ # duplicate and sum 1st copy, s(n)+s(n+1) s¦ # cut away the first element of 2nd copy, s(n) ìì # prepend both to list ¨ # remove last item in list R2£ # reverse and take the first 2 elements '/ý # format output # implicitly print

Try it online

Saved 2 bytes thanks to Adnan.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Does this also work?: XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý. \$\endgroup\$ Commented Aug 18, 2016 at 14:47
  • \$\begingroup\$ @Adnan Indeed. I forgot that ý can format a list. Nice. \$\endgroup\$ Commented Aug 18, 2016 at 14:51
4
\$\begingroup\$

MATL, 20 bytes

FT+"@:qtPXnosV47]xhh

This uses the characterization in terms of binomial coefficients given in the OEIS page.

The algorithm works in theory for all numbers, but in practice it is limited by MATL's numerical precision, and so it doesn't work for large entries. The result is accurate for inputs up to 20 at least.

Try it online!

Explanation

FT+ % Implicitly take input n. Add [0 1] element-wise. Gives [n n+1] " % For each k in [n n+1] @:q % Push range [0 1 ... k-1] tP % Duplicate and flip: push [k-1 ... 1 0] Xn % Binomial coefficient, element-wise. Gives an array os % Number of odd entries in that array V % Convert from number to string 47 % Push 47, which is ASCII for '\' ] % End for each x % Remove second 47 hh % Concatenate horizontally twice. Automatically transforms 47 into '\' % Implicitly display
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 2, 85 81 bytes

x,s=input(),[1,1] for i in range(x):s+=s[i]+s[i+1],s[i+1] print`s[x-1]`+"/"+`s[x]`

This submission is 1-indexed.

Using a recursive function, 85 bytes:

s=lambda x:int(x<1)or x%2 and s(x/2)or s(-~x/2)+s(~-x/2) lambda x:`s(x)`+"/"+`s(x+1)`

If an output like True/2 is acceptable, here's one at 81 bytes:

s=lambda x:x<1 or x%2 and s(x/2)or s(-~x/2)+s(~-x/2) lambda x:`s(x)`+"/"+`s(x+1)`
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

C (GCC), 79 bytes

Uses 0-based indexing.

s(n){return!n?:n%2?s(n/2):s(-~n/2)+s(~-n/2);}r(n){printf("%d/%d",s(n),s(n+1));}

Ideone

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ x?:y is a gcc extension. \$\endgroup\$ Commented Aug 20, 2016 at 6:00
3
\$\begingroup\$

Jelly, 14 bytes

3ẋḶŒpḄċ ’Ç”/⁸Ç

Try it online!

Ooh, looks like I can beat the accepted answer by @Dennis, and in the same language at that. This works using a formula from OEIS: the number of ways to express (the number minus 1) in hyperbinary (i.e. binary with 0, 1, 2 as digits). Unlike most Jelly programs (which work either as a full program or a function), this one works only as a full program (because it sends part of the output to stdout, and returns the rest; when used as a full program the return value is sent to stdout implicitly, so all the output is in the same place, but this wouldn't work for a function submission).

This version of the program is very inefficient. You can create a much faster program that works for all input up to 2ⁿ via placing n just after the ẋ on the first line; the program has O(n × 3ⁿ) performance, so keeping n small is fairly important here. The program as written sets n equal to the input, which is clearly large enough, but also clearly too large in almost all cases (but hey, it saves bytes).

Explanation

As usual in my Jelly explanations, text in braces (e.g. {the input}) shows something that automatically filled in by Jelly due to missing operands in the original program.

Helper function (calculates the nth denominator, i.e. the n+1th numerator):

3ẋḶŒpḄċ 3ẋ 3, repeated a number of times equal to {the argument} Ḷ Map 3 to [0, 1, 2] Œp Take the cartesian product of that list Ḅ Convert binary (or in this case hyperbinary) to a number ċ Count number of occurrences of {the argument} in the resulting list

The first five bytes are basically just generating all possible hyperbinary numbers up to a given length, e.g. with input 3, the output of Ḷ is [[0,1,2],[0,1,2],[0,1,2]] so the cartesian product is [[0,0,0],[0,0,1],[0,0,2],[0,1,0],…,[2,2,1],[2,2,2]]. Ḅ basically just multiplies the last entry by 1, the penultimate entry by 2, the antepenultimate entry by 4, etc., and then adds; although this is normally used to convert binary to decimal, it can handle the digit 2 just fine, and thus works for hyperbinary too. Then we count the number of times the input appears in the resulting list, in order to get an appropriate entry in the sequence. (Luckily, the numerator and denominator follow the same sequence).

Main program (asks for the numerator and denominator, and formats the output):

’Ç”/⁸Ç ’Ç Helper function (Ç), run on {the input} minus 1 (‘) ”/ {Output that to stdout}; start again with the constant '/' ⁸Ç {Output that to stdout}; then run the helper function (Ç) on the input (⁸)

Somehow I keep writing programs that take almost as many bytes to handle I/O as they do to solve the actual problem…

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Good grief, you weren't kidding about it being inefficient - on TIO 12 takes 20s to complete, and 13 times out completely! Accepted, even though I can't verify all the test cases. \$\endgroup\$ Commented Feb 16, 2017 at 9:00
3
\$\begingroup\$

JavaScript (ES6), 43 bytes

f=(i,n=0,d=1)=>i?f(i-1,d,n+d-n%d*2):n+'/'+d

1-indexed; change to n=1 for 0-indexed. The linked OEIS page has a useful recurrence relation for each term in terms of the previous two terms; I merely reinterpreted it as a recurrence for each fraction in terms of the previous fraction. Unfortunately we don't have inline TeX so you'll just have to paste it onto another site to find out how this formats:

$$ \frac{a}{b} \Rightarrow \frac{b}{a + b - 2(a \bmod b)} $$

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

m4, 131 bytes

define(s,`ifelse($1,1,1,eval($1%2),0,`s(eval($1/2))',`eval(s(eval(($1-1)/2))+s(eval(($1+1)/2)))')')define(r,`s($1)/s(eval($1+1))')

Defines a macro r such that r(n) evaluates according to the spec. Not really golfed at all, I just coded the formula.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 124 bytes \$\endgroup\$ Commented Apr 8, 2021 at 12:51
3
\$\begingroup\$

Python 2, 66 bytes

f=lambda n:1/n or f(n/2)+n%2*f(-~n/2) lambda n:`f(n)`+'/'+`f(n+1)`

Uses the recursive formula.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Actually, 18 bytes

11,`│;a%τ@-+`nk'/j

Try it online!

This solution uses Peter's formula and is likewise 0-indexed. Thanks to Leaky Nun for a byte.

Explanation:

11,`│;a%τ@-+`nk'/j 11 push 1, 1 ,`│;a%τ@-+`n do the following n times (where n is the input): stack: [t s] │ duplicate the entire stack ([t s t s]) ; dupe t ([t t s t s]) a invert the stack ([s t s t t]) % s % t ([s%t s t t]) τ multiply by 2 ([2*(s%t) s t t]) @- subtract from s ([s-2*(s%t) s t]) + add to t ([t+s-2*(s%t) t]) in effect, this is s,t = t,s+t-2*(s%t) k'/j push as a list, join with "/"
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ A controversial byte off \$\endgroup\$ Commented Aug 20, 2016 at 8:44
  • \$\begingroup\$ @LeakyNun I'll hold off on that improvement until there's clarification from the OP. \$\endgroup\$ Commented Aug 20, 2016 at 8:45
3
\$\begingroup\$

Maple

0: do 1/(1+floor(%)-frac(%))od;

Uses % which is the ditto operator reevaluating the last expression.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, nice first answer! \$\endgroup\$ Commented Jan 8, 2021 at 16:28
2
\$\begingroup\$

MATL, 32 30 bytes

1i:"tt@TF-)sw@)v]tGq)V47bG)Vhh

This uses a direct approach: generates enough members of the sequence, picks the two desired ones and formats the output.

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

R, 93 bytes

f=function(n)ifelse(n<3,1,ifelse(n%%2,f(n/2-1/2)+f(n/2+1/2),f(n/2))) g=function(n)f(n)/f(n+1)

Literally the simplest implementation. Working on golfing it a bit.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Ruby, 49 bytes

This is 0-indexed and uses Peter Taylor's formula. Golfing suggestions welcome.

->n{s=t=1;n.times{s,t=t,s+t-2*(s%t)};"#{s}/#{t}"}
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 108 106 101 bytes

(s={1,1};n=1;a=AppendTo;t=ToString;Do[a[s,s[[n]]+s[[++n]]];a[s,s[[n]]],#];t@s[[n-1]]<>"/"<>t@s[[n]])&
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 56 bytes (SBCS)

{1(⍵{s←⍺⊃⍵⋄t←⍵[n←⍺+1]⋄⍺=⍺⍺:,/⍕¨s'/'t⋄n∇⍵,(s+t),t})1 1}

Try it online!

Inner operator:

{ ⍝ ⍺ is counter, ⍺⍺ is input, ⍵ is sequence s ← ⍺ ⊃ ⍵ ⍝ s is the ⍺th element of ⍵ (1-indexed), i.e. s(n) ⋄t ← ⍵[n←⍺+1] ⍝ t is s(n+1). Also create variable n that holds ⍺+1 ⋄⍺ = ⍺⍺: ⍝ If counter equals the n we want to reach s ÷ t ⍝ Return s(n) / s(n+1) ⋄n ∇ ⍵,(s+t),t ⍝ Otherwise, call itself again with counter incremented ⍝ and the new terms added to the sequence ⍝ ∇ is self reference and , is concatenate }

The outer function just calls the inner one with 1 as the initial value of the counter, 1 1 as the initial sequence, and its right argument as the left operand of the inner operator (n).

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

TI-BASIC (TI-83 Plus), 69 bytes

1→D Input I For(J,1,I D→E N+D-2(N-Dint(N/D→D E→N End 2+int(log(N Output(1,1,N Output(1,Ans,"/ Output(1,Ans+1,D

assuming you clear your memory after every run of the program. outputs in the top left

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

><>, 34+2 = 36 bytes

After seeing Peter Taylor's excellent answer, I re-wrote my test answer (which was an embarrassing 82 bytes, using very clumsy recursion).

&01\$n"/"on; &?!\:@}:{:@+@%2*-&1-:

It expects the input to be present on the stack, so +2 bytes for the -v flag. Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Octave, 90 bytes

function f(i)S=[1 1];for(j=1:i/2)S=[S S(j)+S(j+1) (j+1)];end;printf("%d/%d",S(i),S(i+1));end
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C#, 91 90 bytes

n=>{Func<int,int>s=_=>_;s=m=>1==m?m:s(m/2)+(0==m%2?0:s(m/2+1));return$"{s(n)}/{s(n+1)}";};

Casts to Func<int, string>. This is the recursive implementation.

Ungolfed:

n => { Func<int,int> s = _ => _; // s needs to be set to use recursively. _=>_ is the same byte count as null and looks cooler. s = m => 1 == m ? m // s(1) = 1 : s(m/2) + (0 == m%2 ? 0 // s(m) = s(m/2) for even : s(m/2+1)); // s(m) = s(m/2) + s(m/2+1) for odd return $"{s(n)}/{s(n+1)}"; };

Edit: -1 byte. Turns out C# doesn't need a space between return and $ for interpolated strings.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 59 bytes

s,t=1,1;exec"s,t=t,s+t-2*(s%t);"*input();print'%d/%d'%(s,t)

Uses Peter's formula and is similarly 0-indexed.

Try it online

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 29 bytes

([,'/',])&":&([:+/2|]!&i.-)>:

Usage

Large values of n require a suffix of x which denotes the use of extended integers.

 f =: ([,'/',])&":&([:+/2|]!&i.-)>: f 1 1/1 f 10 3/5 f 50 7/12 f 100x 7/19 f 1000x 11/39
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 100 counts as a "large value"? \$\endgroup\$ Commented Aug 22, 2016 at 14:11
  • 1
    \$\begingroup\$ @dcsohl In this method, the binomial coefficients are computed, and for n = 100, the largest one computed is C(72, 28) = 75553695443676829680 > 2^64 and will require extended integers to avoid floating point values. \$\endgroup\$ Commented Aug 22, 2016 at 15:16
1
\$\begingroup\$

R, 84 bytes

function(n,K=c(1,1)){for(i in 1:n)K=c(K,K[i]+K[i+1],K[i+1]) paste0(K[i],"/",K[i+1])}

Try it online!

The older R implementation doesn't follow the specs, returning a floating point rather than a string, so here's one that does.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 33 bytes

f(n)=if(n,(1+f(n\2)^q=n%2*2-1)^q)

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Desmos, 212 bytes

Try it online! (link 1) Try it online! (link 2) (just please note that due to Desmos' max recursion limit, you'll have to wait quite some time just to get the function to even load values properly)

s\left(n\right)=\left\{n=1:1,\operatorname{mod}\left(n,2\right)=0:s\left(\frac{n}{2}\right),s\left(\frac{n-1}{2}\right)+s\left(\frac{n+1}{2}\right)\right\} r\left(n\right)=\frac{s\left(n\right)}{s\left(n+1\right)}

Readable version:

s(n)={n=1:1,mod(n,2)=0:s(n/2),s((n-1)/2)+s((n+1)/2)} r(n)=s(n)/s(n+1)

How does it work? Well, we can define recursive functions in Desmos:$$s(n)=\{n=1:1,\operatorname{mod}(n,2)=0:s(n/2),s((n-1)/2)+s((n+1)/2)\}$$and now all we have to do is create \$r(n)=\frac{s(n)}{s(n+1)}\$, and we're done!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 49 chars

r←f w;k r←1x⋄→0×⍳w≤1⋄r←1+k←f⌊w÷2⋄→0×⍳2∣w⋄r←÷1+÷k

It seems r(x)=(1 if x=1;1+r((x-1)/2) if x is odd;1/(1+1/r(x/2)) if x is even)

"⌊w÷2" is ok as "w÷2" if w is even, or "(w-1)÷2" if w is odd.

1x or 1 with type rational is the base of induction, and from this value are built all other values that maintain the same type of base of induction.

//8+41=49

 f ¨⍳10 1 1r2 2 1r3 3r2 2r3 3 1r4 4r3 3r5 f 100 7r19 f 1000 11r39
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

YASEPL, 51 bytes

=d$=n=i'=j$`1=e$d=z$n%d*!-z+n!n$e!j+}4,i#n#divide>d

explanation:

=d$=n=i'=j$`1=e$d=z$n%d*!-z+n!n$e!j+}4,i#n#divide>d packed =d$ denominator = d = 1 =n numerator = n = 0 =i' get input, set to i =j$`1 }4,i j = 1, while j < i... =e$d e = d =z$n%d* z = (n%d)*2 !-z+n d = d - z + n !n$e n = e !j+ increment j #n#divide>d output fraction
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.