The Stern-Brocot sequence is a Fibonnaci-like sequence which can be constructed as follows:
- Initialise the sequence with
s(1) = s(2) = 1
- Set counter
n = 1
s(n) + s(n+1)to the sequence
s(n+1)to the sequence
n, return to step 3
This is equivalent to:
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
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
bare the relevant entries in the Stern-Brocot sequence. Evaluating the fraction before output is not permissable. For example, for input
12, output should be
- Standard loopholes are disallowed
This is code-golf, so shortest answer in bytes will win.
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