Encuentra en qué nivel del árbol de Calkin-Wilf está un número

Question

El Calkin–Wilf árbol es un árbol de fracciones de donde conseguir los dos nodos secundarios, el primer hijo (el padre del numerador / x) y el segundo niño es (x / el padre del denominador), donde x es la suma de los padres del numerador y del denominador. (Esta parte fue añadido más tarde por lo que esta pregunta es la búsqueda de poder)

Se parece a esto cuando las fracciones se expresan como coordenadas:

$$ \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}$ como entrada).

Answer 1

El árbol es conocido como el Calkin-Wilf árbol (https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree)

Si $a$ $b$ son relativamente primos, no es exactamente una forma de llegar desde $(1,1)$$(a,b)$; de lo contrario, el par $(a,b)$ no es accesible.

Supongamos $a < b$ (el otro caso es similar). Si los pasos en el algoritmo de Euclides para encontrar $\gcd(a,b)$

$\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)$ por separado.

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

Deje $h(x,y)$ el número de pasos necesarios para llegar a la par $(x,y)$, suponiendo que esto es posible, o $h(x,y) = -1$ si $(x,y)$ no es accesible.

Claramente $h(x,y) = h(y,x)$, ya que siempre se puede añadir en cualquier dirección, por lo que podemos muy bien suponer $x \leq y$ cuando la evaluación de esta función.

También, si $x$ o $y$ es de menos de $1$,$h(x,y) = -1$. Y, por supuesto, también sabemos $h(1,1) = 0$.

De hecho, supongo que sabes que $h(1, x) = x-1$ para todos los enteros positivos $x$ (como usted mismo ha señalado!) puesto que la única manera de llegar a $(1,x)$ es varias veces la adición de $1$ para el segundo valor de tu pareja.

OK. Asumiendo $a \leq b$, ¿cómo puede llegar a $(a,b)$? Bien, el último paso tendría que ser $(a, b-a) \to (a,b)$, porque en el $(a-b, b) \to (a,b)$ no sería posible (desde $a-b \leq 0$).

Así que ahora, considere el siguiente código en Python (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

Básicamente, el número de pasos para llegar a $(a,b)$, es, sin embargo, muchos de los pasos que toma para llegar a $(a, b-a)$,$1$. (A menos que $(a, b-a)$ es imposible, en cuyo caso $(a,b)$ es, también.)

Pero si nos fijamos en este código para un poco de tiempo, te das cuenta de que es un poco ineficiente: si $b-a$ todavía es al menos tan grande como $a$, entonces sólo tendremos que restar $a$ nuevo. De hecho, vamos a mantener restando $a$ hasta llegar a algo menos de $a$. Ese resultado (el número inferior a $a$) se llama el RESTO cuando se divide $b$$a$, y el número de veces que restar $a$ se llama el COCIENTE.

Así, se podría mejorar el código de algo:

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

En este punto, espero que usted será capaz de ver cómo Catalin Zara la respuesta de obras.

Answer 3

Después de leer la página de la Wikipedia proporcionada por @Catalin Zara, he implementado una solución alternativa. Yo no soy el de matemáticas y el tipo, así que puede haber malinterpretado su solución

De acuerdo a https://en.wikipedia.org/wiki/Calkin-Wilf_tree:

El Calkin–Wilf es la secuencia de la secuencia de los números racionales generado por una anchura transversal de la Calkin–Wilf árbol,

$$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, …. $$ [...] El uso de la continuación de la fracción de los $q_i$ como la duración de la codificación de un número binario se da vuelta $i$ sí.
Ejemplo:
$q_{i}=3/4$: La continuación de la fracción es [0;1,3] por lo tanto $i = 1110_2 = 14$.
$q_{i}=4/3$: La continuación de la fracción es [1;3]. Pero para utilizar este método de la longitud de la continuación de la fracción debe ser un número impar. Así que [1;3] debe sustituirse por el equivalente continuo de la fracción [1;2,1]. Por lo tanto $i = 1001_{2} = 9$.

Para llegar tan lejos hacia abajo de un árbol $q_i$, ya que hay $2^{level}$ nodos en cada nivel, usted haría $\log_2{i} - 1$.
Desde $i$ siempre comienza con $1$ base $2$, cada dígito adicional de $i$ en binario agregará $1$$\log_2{i}$.
Esto significa que para obtener el nivel de el árbol de un número, gire a la $\frac a b$ en un continuo fracción, encontrar la suma de las partes de la continuación de la fracción y restar $1$.

Así, un programa en Python para hacer esto sería:

try:
    from math import gcd
except ImportError:  # In Python 2, gcd is implemented slowly in fractions
    from fractions import gcd

def minimise(a, b):
    if gcd(a, b) != 1:
        return -1  # If they aren't coprime, a / b is not simplest form

    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

    return level