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:

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Mathematics

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
	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:
			a -= b
			path = '1' + path
		else:
			b -= a
			path = '0' + path
	base = 2 ** len(path) - 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


def rat_at(n):
	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):
	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)
	line = 1
	tot = 0
	while tot <= n:
		tot += 2 ** line
		line += 1
	if line > 1:
		line -= 1
	route = ''
	b = 2 ** line
	pos = n + 1 - 2 ** line
	while b > 1:
		if pos < b // 2:
			route += 'l'
			b = b // 2
		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