Find what level of the Calkin–Wilf tree a number is on The Calkin–Wilf tree is a tree of fractions where to get the two child nodes, the first child is (the parent's numerator / x) and the second child is (x / the parent's denominator), where x is the sum of the parent's numerator and denominator. (This part was added later so this question is more search-able)
It looks like this when the fractions are expressed as coordinates:
$$
\newcommand{\r}{→}
\newcommand{\s}{\quad}
\begin{align}
&(1, 1) \r \\
&\s(1, 2) \r \\
&\s\s(1, 3) \r \\
&\s\s\s(1, 4) \r\ \dots \\
&\s\s\s(4, 3) \r\ \dots \\
&\s\s(3, 2) \r \\
&\s\s\s(3, 5) \r\ \dots \\
&\s\s\s(5, 2) \r\ \dots \\
&\s(2, 1) \r \\
&\s\s(2, 3) \r \\
&\s\s\s(2, 5) \r\ \dots \\
&\s\s\s(5, 3) \r\ \dots \\
&\s\s(3, 1) \r \\
&\s\s\s(3, 4) \r\ \dots \\
&\s\s\s(4, 1) \r\ \dots
\end{align}
$$
So, I would like to find out if there is an algorithm to find the minimum number of times the rule has to be applied to get to a certain number.
Here are some patterns I have noticed (Where you are trying to get to $(a, b)$, and the function that returns the minimum times is $f(a, b)$, which is $-1$ where it is impossible)
f(a, b) = f(b, a)
f(1, b) = b - 1
f(a, a) = -1 (except when a = 1, as f(1, 1) = 0)
f(2, b) = -1 if b is even, else ceil(b / 2)
f(<prime number>, b) = -1 iff b is a multiple of a
f(3, b) = (-1 iff (b is a multiple of 3)), else (floor(n / 3) + 2)

If you arrange them in a table (Download here)
Rows are the same columns, as a and b can be reversed.
The diagonals from the top-left to the bottom-right are the same as a row / column.

I can make some brute-force code (In Python)
def minimise(a, b):
    if a < 1 > b:
        return -1
    possible = {(1, 1)}
    target = (a, b)
    i = 0
    get_nexts = next_getter_factory(target)

    while possible and target not in possible:
        possible = {next_pos for pos in possible for next_pos in get_nexts(*pos)}
        i += 1

    if not possible:
        return -1

    return i

def next_getter_factory(target):
    A, B = target
    def get_nexts(a, b):
        if a + b <= B:
            yield (a + b, b)
        if a + b <= A:
            yield (a, a + b)
    return get_nexts

This has the one optimization that it won't check a possibily if one of it's values is already above the target value, but there is probably some math that can make this happen in a reasonable amount of time with large input (I am expecting values up to $2^{128}$ as input).

After reading the Wikipedia page provided by @Catalin Zara, I have implemented an alternate solution. I am not the math-y type, so I may have misinterpreted their solution
According to https://en.wikipedia.org/wiki/Calkin-Wilf_tree:

The Calkin–Wilf sequence is the sequence of rational numbers generated by a breadth-first traversal of the Calkin–Wilf tree,
$$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, …. $$
  [...]
  Using the continued fraction of any $q_i$ as the run-length encoding of a binary number gives back $i$ itself.
  Example:
  $q_{i}=3/4$: The continued fraction is [0;1,3] hence $i = 1110_2 = 14$.
  $q_{i}=4/3$: The continued fraction is [1;3]. But to use this method the length of the continued fraction must be a odd number. So [1;3] should be replaced by the equivalent continued fraction [1;2,1]. Hence $i = 1001_{2} = 9$.

To get how far down a tree $q_i$, since there are $2^{level}$ nodes at each level, you would do $\log_2{i} - 1$.
Since $i$ always starts with $1$ in base $2$, each extra digit of $i$ in binary will add $1$ to $\log_2{i}$.
This means to get the level of the tree a number is at, you turn $\frac a b$ into a continued fraction, find the sum of the parts of the continued fraction and subtract $1$.
So, a Python program to do this would be:
def minimise(a, b):
    level = -1
    while b:
        cont, a = divmod(a, b)
        level += cont  # cont is the next item in the continued fraction
        a, b = b, a  # Swapping is the same as the reciprocal
    # This also acts as the Euclidean algorithm, where if a != 1,
    # a / b is not in their simplest form (As a is their GCD)
    if a != 1:
        return -1
    return level

