¿Existe algún algoritmo elegante que enumere un número arbitrario de números racionales entre 0 y 1 sin repetir ninguno? ¿Está relacionado con...

Si.

Existe un algoritmo simple y elegante que emite números racionales entre 00 y 11, todos ellos, sin repetición, sin necesidad de reducir fracciones, sin necesidad de verificar que sea primo relativo, y sin siquiera usar multiplicación o división o el algoritmo euclidiano. Todo lo que necesita hacer es copiar y agregar números. (Entonces, en particular, no, no hay relación con encontrar el siguiente número primo, que es una tarea mucho más difícil).

Aquí está.

1. Escriba los números 0,10,1. Ponga el dedo en el 1.

 0 1 
   I 

(La I muestra dónde esta el dedo)

2) Copie el número bajo el dedo. Llámelo aa

 0 1 1 
   I a 

3) Añada el número bajo el dedo con el de la derecha. Llámelo bb

 0 1 1 2 
   I a b 

4) Escriba el numero racional \frac{a}{b}. Ahora puede olvidar aa y bb

5) Mueva su dedo a la derecha y regrese al paso 2).

0 1 1 2 
    I 

Eso es todo.

No, enserio. Eso es todo. Este algoritmo no requiere nada mas que tener un dedo, copiar y sumar. Nos da todos los números racionales entre el 00 y el 11, una sola vez. Es difícil de imaginar un algoritmo más simple para hacer cualquier cosa, y es muy satisfactorio que algo tan natural como escribir los números racionales tenga un procedimiento tan simple.

Sorprendentemente, este algoritmo fue descubierto en 1999 (Véase Recounting the Rationals, por y Wilf, disponible aquí http://www.math.upenn.edu/~wilf/website/recounting.pdf)

Así es como se ven los primeros pasos, con la barra azul que representa nuestro dedo.

La secuencia producida por este algoritmo es la siguiente( A002487 - OEIS)

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, … 

Se la conoce como secuencia diatómica de Stern, secuencia de Stern-Brocot, secuencia de Calkin-Wilf, función fusc y probablemente otros nombres. Los primeros 10241024 términos de la secuencia se ven bastante interesantes:

Aquí está un simple código para producir esta gráfica: Sage Cell Server

Si toma pares de números consecutivos en esta secuencia y los ve como fracciones, obtiene todos los números racionales positivos, no solo los que están entre 00 y 11. Para entender lo que pregunta esta pregunta, simplemente me salté todas las demás fracciones. Tenemos 0101 (que también omití ya que interpreté "entre 00 y 11" como excluyendo los puntos finales), omití 1111, toma 1212, omita 2121, tome 1313, omita 32,32,se repíte.

La forma más fácil de entender por qué esto funciona es estudiar el árbol de Calkin-Wilf[1] , que organiza los números racionales positivos mediante un procedimiento muy simple:

Iniciando en 1111 como la raíz, obtienes esto:

fuente:(Calkin–Wilf tree - Wikipedia)

Si lee los números en este árbol fila por fila, de izquierda a derecha, reconociendo que cada denominador es el mismo que el siguiente numerador, obtiene la secuencia de Stern que acabamos de discutir.

Acaso no es genial

Notas al pie