¿Cuál es la forma más eficiente de enumerar todos los números racionales?

Answer 1

Si [math] f: \ mathbb {N} \ rightarrow \ mathbb {Z} [/ math] (donde [math] \ mathbb {N} [/ math] denota el conjunto de enteros positivos, incluido 0) es una biyección del números naturales a los enteros, entonces podemos crear una biyección [math] g: \ mathbb {Z} \ rightarrow \ mathbb {Q} [/ math]: escribe el argumento n como producto de primos (y -1), y realizar [matemáticas] f [/ matemáticas] en los exponentes. Por supuesto, [math] g \ circ f [/ math] puede usarse para enumerar directamente los racionales.

Por ejemplo, si [matemática] f [/ matemática] es la función de modo que [matemática] f (n) = (n + 1) / 2 [/ matemática] para valores impares de n , y [matemática] f (n) = -n / 2 [/ math] para valores pares, luego [math] g \ circ f [/ math] se asigna de la siguiente manera:
n 0 1 2 3 4 5 6 7 8 9 10 11 12
f (n) 0 1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
g (f (n)) 0 1 -1 2 -2 3 -3 1/2 -1/2 5 -5 6 -6

Este método es muy sencillo y es fácil encontrar los elementos correspondientes en cualquier dirección, ya que no se define de forma recursiva. La desventaja es que encontrar factores primos es difícil.

Por ejemplo, el índice de 25/11, o 5 ^ 2 * 11 ^ -1, se encuentra fácilmente en 30249, sin tener que calcular todos los números anteriores.

Answer 2

Este código de Python que enumera el árbol Calkin-Wilf que mencionó Tom McFarlane calcula cada elemento únicamente a partir de la representación binaria de su posición en la secuencia, por lo que no tiene en cuenta los valores anteriores.

def leaf2frac(leaf,m=0,n=1): for bit in leaf: if bit=='0': n += m if bit=='1': m += n return str(m)+'/'+str(n) for i in xrange(32): leaf = format(i,'b') print i,leaf,leaf2frac(leaf) 

Utiliza el inverso del algoritmo euclidiano para calcular el máximo común divisor de dos números. Dado un par de enteros, restar uno del otro da un par con el mismo MCD. Después de un número finito de pasos restando el que sea mayor, el algoritmo euclidiano alcanza solo el GCD y 0.

Para poner una fracción en forma reducida, encuentre el MCD del numerador y el denominador, luego factorícelo a partir de ambos. Si el MCD es 1, la fracción ya está en forma reducida.

En el proceso inverso, comience con 1 como el MCD y vuelva a construir el par agregando repetidamente un número al otro. Debido a que GCD sigue siendo 1, tenemos garantizada una fracción reducida. Debido a que la única opción en cada paso es cuál agregar al otro, podemos representar la opción como un dígito binario. Al enumerar números binarios, podemos alcanzar cada secuencia finita de opciones. Los ceros iniciales no tienen efecto ya que simplemente agregan m = 0 a n = 1 sin efecto, antes de que comience el cálculo no trivial.

El resultado es:

  0 0 0/1
 1 1 1/1
 2 10 1/2
 3 11 2/1
 4 100 1/3
 5 101 3/2
 6 110 2/3
 7 111 3/1
 8 1000 1/4
 9 1001 4/3
 10 1010 3/5
 11 1011 5/2
 12 1100 2/5
 13 1101 3/3
 14 1110 3/4
 15 1111 4/1
 16 10000 1/5
 17 10001 5/4
 18 10010 4/7
 19 10011 7/3
 20 10100 3/8
 21 10101 8/5
 22 10110 5/7
 23 10111 7/2
 24 11000 2/7
 25 11001 7/5
 26 11010 5/8
 27 11011 3/8
 28 11100 3/7
 29 11101 7/4
 30 11110 4/5
 31 11111 1/5

Answer 3

La secuencia de Calkin-Wilf, es decir, un recorrido transversal del árbol de Calkin-Wilf, genera una lista de todos los racionales positivos sin ningún duplicado. No tengo idea de si esta es la forma más eficiente de enumerar todos los racionales, pero parece bastante simple.