Find what level of the Calkin–Wilf tree a number is on

Question

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).

Answer 1

The tree is known as the Calkin-Wilf tree (https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree)

If $a$ and $b$ are relatively prime, there is exactly one way to get from $(1,1)$ to $(a,b)$; otherwise, the pair $(a,b)$ is not reachable.

Suppose $a < b$ (the other case is similar). If the steps in the Euclidean algorithm to find $\gcd(a,b)$ are

$\begin{align*} b & =q_1 a + r_1 \\ a & = q_2r_1 + r_2 \\ \vdots & = \vdots \\ r_m & = q_{m+2} r_{m+1} + r_{m+2} = q_{m+2}r_{m+1}+1 \\ r_{m+1} & = q_{m+3} \cdot 1 + 0 \end{align*}$

then the number of steps to get from $(1,1)$ to $(a,b)$ is $q_1+q_2 + \dotsb + q_{m+3} -1$.

Added: the python program below computes the level by keeping track of the subtractions involved in the Euclidean algorithm. There is no need to compute $\gcd(a,b)$ separately.

def steps(a,b):
    level = -1
    while a > 0:
        while a <= b:
            a, b = a, b - a
            level += 1
        a, b = b, a
    if b == 1:
        return level
    else:
        return -1

Answer 2

Let $h(x,y)$ be the number of steps required to get to the pair $(x,y)$, assuming this is possible, or $h(x,y) = -1$ if $(x,y)$ is not reachable.

Clearly $h(x,y) = h(y,x)$, since you can always add in either direction, so we may as well assume $x \leq y$ when evaluating this function.

Also, if either $x$ or $y$ is less than $1$, then $h(x,y) = -1$. And of course we also know $h(1,1) = 0$.

In fact, I guess we know that $h(1, x) = x-1$ for all positive integers $x$ (as you yourself pointed out!) since the only way to get to $(1,x)$ is by repeatedly adding $1$ to the second value in your pair.

OK. Assuming $a \leq b$, how could you possibly get to $(a,b)$? Well, your last step would have to be $(a, b-a) \to (a,b)$, because going $(a-b, b) \to (a,b)$ wouldn't be possible (since $a-b \leq 0$).

So now consider the following Python code (Python 2):

def h(a, b):
    if a > b:
        return h(b, a) #can assume a <= b
    if a < 1:
        return -1 #can assume 1 <= a <= b
    if a == 1:
        return b - 1
    k = h(a, b - a)
    if k == -1:
        return -1
    return 1 + k

Basically, the number of steps to reach $(a,b)$, is however many steps it takes to reach $(a, b-a)$, plus $1$. (Unless $(a, b-a)$ is impossible, in which case $(a,b)$ is, too.)

But if you look at this code for a little while, you'll realize that it's a little inefficient: if $b-a$ is still at least as big as $a$, then we'll just subtract $a$ again. In fact we'll keep subtracting $a$ until we get to something less than $a$. That result (the number that's less than $a$) is called the REMAINDER when we divide $b$ by $a$, and the number of times we subtract $a$ is called the QUOTIENT.

So we could improve the code somewhat:

def h(a, b):
    if a > b:
        return h(b, a) #can assume a <= b
    if a < 1:
        return -1 #can assume 1 <= a <= b
    if a == 1:
        return b - 1
    q, r = divmod(b, a)
    k = h(r, a) #now r < a
    if k == -1:
        return -1
    return q + k

At this point, hopefully you'll be able to see how Catalin Zara's response works.

Answer 3

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