4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ According to the Wikipedia page, "If a/b < 1, the parent of a/b is a/(b − a); if a/b is greater than one, the parent of a/b is (a − b)/b.". So, a non-recursive implementation of that is: pastebin.com/FXnQWwdf $\endgroup$ – Artyer Dec 23 '16 at 22:12
  • $\begingroup$ @Artyer You're right, you can do this in a while-loop. (Although your code at the link above doesn't seem to be working quite right at the moment: doing h(1,3) seems to return 0.) Anyway, I agree that my code should not be considered "good"...but I thought it might be helpful to explain how/why the process worked, for someone who's comfortable reading Python code. (FYI, this process is essentially the "Euclidean algorithm" for calculating the gcd of two integers, with a little special-casing in case one of the input values is 1.) $\endgroup$ – mathmandan Dec 23 '16 at 22:59
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.