Here's a way to construct a list containing every positive rational number:

Build a binary tree where each node is a rational and the root is `1/1`, with the following rules for creating the nodes below:
* The value of the left-hand node below `a/b` is `a/a+b`
* The value of the right-hand node below `a/b` is `a+b/b`

So the tree will look like this:

```
                       1/1
                  /           \ 
            1/2                  2/1
           /    \              /     \
       1/3        3/2        2/3       3/1
      /   \      /   \      /   \     /   \
   1/4    4/3  3/5   5/2  2/5   5/3  3/4   4/1
 
 ...
```

Now traverse the tree, breadth first, to get a list of rationals.

```
[ 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, .. ]
```

Every positive rational will occur, in its reduced form, exactly once in the list, at a finite index.

```if:haskell
In the kata, we will use tuples of type `(Integer, Integer)` to represent rationals, where `(a, b)` represents `a / b`
```
```if:javascript
In the kata, we will use tuples of type `[ Number, Number ]` to represent rationals, where `[a,b]` represents `a / b`
```

Using this method you could create an infinite list of tuples:

matching the list described above:

However, constructing the actual list is too slow for our purposes. Instead, study the tree above, and write two functions:

For example:

Difficulty: introductory

Starter code:

def rat_at(n):
	

Solutions:
def rat_at(n):
    if n == 0:
        return 1, 1
    a, b = rat_at((n - 1) // 2)
    return (a, a + b) if n % 2 else (a + b, b)

def index_of(a, b):
    if a == b == 1:
        return 0
    return 2 * index_of(a, b - a) + 1 if b > a else 2 * index_of(a - b, b) + 2

from math import ceil
def rat_at(n):
    if n==0:return (1,1)
    a,b=rat_at(max(ceil(n/2)-1,0))
    return (a,b+a) if n%2 else (a+b,b)

def index_of(a,b):
    if a==b==1:return 0
    elif a<b:return index_of(a,b-a)*2+1
    else: return (index_of(a-b,b)+1)*2

seq = {0: 1, 1:1}

def fusc(n):
    if n in list(seq.keys()):
        return seq[n]
    elif n%2 == 0:
        r = fusc(n>>1) 
        seq[n] = r
        return r    
    return fusc((n - 1)>>1) + fusc((n + 1)>>1)


def rat_at(n):    
    return fusc(n + 1), fusc(n+2)

def index_of(p, q):
    bits = ''
    while p > 1 or q >1:
        if p>q:
            bits = "1"+ bits
            p = p-q
        else:
            bits = "0"+bits
            q = q-p
    bits = "1" + bits
    return int(bits, 2)-1


def rat_at(n):
    if not n: return (1,1)
    base = 0
    i = n + 1
    while i!=1:
      i= i>>1
      print(i)
      base+=1
    path = str(bin(n - 2**(base)  + 1 ))[2:]
    path = '0'*(base-len(path)) + path # buffer left side w/ 0s
    a=b=1
    path = [x=='1' for x in path]
    for p in path:
      if p: a += b
      else: b += a
    return (a,b)


def index_of(a, b):
    if a==b==1: return 0
    path = ""
    while a!=1 or b!=1:
      if a>b: # from the left, going right
        a-=b
        path = "1" + path
      else: # from the right, going left
        b-=a
        path = "0" + path
    base = 2**len(path) - 2  #int('1'*(count),2)
    addon = int(path,2)+1
    return base + addon

def rat_at(n):
    n = bin(n + 1)
    s = 1
    f = []
    if n[len(n) - 1] == '0':
        f.append(0)
    for i in range(len(n) - 1, 1, -1):
        if n[i] != n[i-1]:
            f.append(s)
            s = 1
        else:
            s += 1
    num = [1, f[len(f) - 1]]
    for i in range(len(f) - 2, -1, -1):
        num[0] = f[i] * num[1] + num[0]
        num[0], num[1] = num[1], num[0]
    num[0], num[1] = num[1], num[0]
    return tuple(num)


def index_of(a, b):
    num = [b, a]
    f = []
    bin = ''
    l = '1'
    while num[0] != 0:
        num[0], num[1] = num[1], num[0]
        f.append(num[0] // num[1])
        num[0] -= f[len(f) - 1] * num[1]
    if len(f) % 2 == 0:
        f[len(f) - 1] -= 1
        f.append(1)
    for n in f:
        bin = (n * l) + bin
        if l == '0':
            l = '1'
        else:
            l = '0'
    return int(bin, 2) - 1


# This is not my code :,(
# I used those functions from here http://240hoursoflearning.blogspot.com/2017/09/the-calkin-wilf-tree.html
# Shame and dishonor on me :,( 

def rat_at(n):
    # This is not my code :,(
    frac = [0, 1]
    n += 1
    nums = [n]

    while n > 0:
        n = n//2
        nums.append(n)

    for n in reversed(nums):    
        if n%2!=0:
            frac[0] += frac[1]

        else:
            frac[1] += frac[0]
    
    return tuple(frac)



def index_of(a, b):
    # This is not my code :,(
    if [a, b] == [1, 1]:
        return 0

    path = ''

    while [a, b] != [1, 1]:
        if a < b:
            b -= a
            path += '0'
        else:
            a -= b
            path += '1'
    addForDepth = 2**len(path)-1

    return addForDepth + int(path[::-1], 2)




import math

def rat_at_layer_pos(layer, pos):
    if layer==pos==0:
        return (1,1)
    else:
        a,b = rat_at_layer_pos(layer-1,pos//2)
        return (a,a+b) if pos%2==0 else (a+b,b)

def rat_at(n):
    layer = len(bin(n+1))-3 if n>0 else 0
    pos = n - int(2**layer-1)
    print(layer, pos)
    return rat_at_layer_pos(layer, pos)

def index_layer_pos(a,b):
    if a==b==1:
        return 0,0
    if a>b:
        l, p = index_layer_pos(a-b,b)
        return l+1, p*2+1
    else:
        l, p = index_layer_pos(a,b-a)
        return l+1, p*2

def index_of(a, b):
    l, p = index_layer_pos(a,b)
    return (2**l-1)+p

def rat_at(n):
    if n == 0:
        return 1,1
    # find line
    line = 1
    tot = 0
    while tot <= n:
        tot += 2**line
        line += 1
    if line > 1:
        line -= 1
    route = ''
    b = 2**line # nr of elements in the line
    pos = n+1 - 2**line # pos in the line
    while b > 1:
        if pos < b // 2:
            route += 'l'
            b = b // 2
            # pos does not change
        else:
            route += 'r'
            b = b // 2
            pos -= b
    a, b = 1, 1
    for c in route:
        if c == 'l':
            a, b = a, a+b
        else:
            a, b = a+b, b
    return a,b

def index_of(a, b):
    aa = a
    bb = b
    route = ''    
    while not (aa == 1 and bb == 1):
        if aa > bb:
            aa = aa-bb
            route = 'r' + route 
        else:
            bb = bb-aa
            route = 'l' + route
    above = 0
    for i in range(len(route)):
        above += 2**i  
    pos = [0,2**len(route)-1]
    for c in route:
        if c == 'l':
            pos[1] = pos[1] - (pos[1]+1 - pos[0]) // 2
        else:
            pos[0] = pos[0] + (pos[1]+1 - pos[0]) // 2
    print(("a: {0}, b: {1}, above: {2}, pos: {3}, route: {4}".format(a,b, above, pos, route)))
    return above+pos[0]
    


def rat_at(n):
    if n == 0:
        return (1, 1)
    for l in range(1001):
        if 2 ** l - 1 <= n <= 2 ** (l + 1) - 2:
            i = l
            break
    if n % 2 == 1:
        j = int((n - (2 ** i - 1)) / 2 + 2 ** (i - 1) - 1)
        k = rat_at(j)
        return (k[0], k[0] + k[1])
    else:
        j = int((n - (2 ** i)) / 2 + 2 ** (i - 1) - 1)
        k = rat_at(j)
        return (k[0] + k[1], k[1])


def index_of(a, b):
    if (a, b) == (1, 1):
        return 0
    if a > b:
        n = index_of(a - b, b)
        k = n
        for l in range(1001):
            if 2 ** l - 1 <= n <= 2 ** (l + 1) - 2:
                i = l
                break
        return k + ((k - (2 ** i - 1)) * 2 + 1 + (2 ** (i + 1) - 1 - k))
    else:
        n = index_of(a, b-a)
        k = n
        for l in range(1001):
            if 2 ** l - 1 <= n <= 2 ** (l + 1) - 2:
                i = l
                break
        return k + ((k - (2 ** i - 1)) * 2 + 1 + (2 ** (i + 1) - 1 - k)) -1


def rat_at(n):
    if n==0: return (1,1)
    a,b=rat_at(~-n>>1)
    return (a,a+b) if n%2 else (a+b,b)


def index_of(a,b):
    if a==1==b: return 0
    return 2*index_of(a,b-a)+1 if a<b else 2*index_of(a-b,b)+2