Para determinar si un entero positivo n finaliza empleando las reglas de la conjetura de Collatz se pueden aprovechar algunas propiedades de los números binarios; y los binarios tienen equivalencias con los booleanos. Por lo tanto parece de lo más natural intentar aplicar directamente operaciones lógicas como reglas.
El conjunto de reglas requiere tres operaciones básicas: (\ x -> x+1), (\ x -> x/2), y (\ x -> 3*x).
Antes que nada supongamos que trabajamos solamente con los impares. En la conjetura de Collatz operar sobre los pares lleva trivialmente a un impar, así que para estos propósitos es conveniente ignorarlos. Primero hace falta una función que convierta enteros a booleanos; esencialmente es una función muy similar a convertir enteros a binarios.
-- Produce la cadena en orden inverso al esperado. Es útil así. decimal_a_bool :: Integer -> [Bool] -- Caso final decimal_a_bool 1 = [True] -- Anamorfismo, recursión de cola decimal_a_bool n = if ((mod n 2) == 0) then False:(decimal_a_bool (div n 2)) else True:(decimal_a_bool (div n 2))
Nótese que produce cadenas que se leen hacia la derecha mientras un binario normalmente se interpreta de derecha a izquierda. Es mejor así porque facilita el acceso al primer elemento.
Ya trabajando en booleanos/quasi-binarios notamos dos hechos significativos: que dividir sobre dos implica retirar un cero en la cabeza de la lista, y que sumar uno se convierte en una operación de inversión en una subcadena. Por ejemplo:
(binarios) s011111 + 1 = s100000 donde s es cualquier cadena de ceros y unos.
Como las reglas implican que después de sumar uno hay que dividir sobre dos, tantas veces como sea posible sin abandonar los enteros, entonces en lugar de invertir los unos se pueden retirar:
(binarios) (s011111 + 1)/2^n (mezclando irreverentemente estructuras...) para n máximo = s100000/2^n = s1.
Implementando para booleanos:
-- En realidad es "mas uno y divide por la mayor potencia de dos que sea factor" mas_uno :: [Bool] -> [Bool] -- Casos finales mas_uno [] = error "mas uno: Sin datos" mas_uno (False:xs) = error "mas_uno requiere impar" -- unidad; 1+1=2, 2/2 = 1 mas_uno [True] = [True] -- Fin del tren de unos mas_uno (True:False:xs) = True:xs -- Recursión de cola -- Recorta todos los unos menos el último antes de un cero mas_uno (True:True:xs) = mas_uno (True:xs)
El algoritmo avanza sobre la lista tirando "Verdaderos" y se detiene cuando encuentra "Verdadero:Falso", sustituyéndolo por un solo "Verdadero" y dejando el resto de la lista intacto. Por fines prácticos calcula como si la lista terminara con una cantidad infinita de elementos "Falso".
Falta una función booleana para (\ x -> 3*x), equivalente a (\ x -> x + (2*x)). Lo que eso significa es que hay que tomar la cadena booleana, desplazarla un elemento y sumarla consigo misma. Por ejemplo:
3 * 100101 (una vez más, abusando de la notación) = 100101 + 1001010. Trasladado a booleanos, la operación '+' se convierte en xor. Se pueden hacer xor elemento por elemento, solamente hay que tener cuidado con los carry resultado de 'Verdadero xor Verdadero'.
En el modelo requerido para Collatz podemos asumir que todas las cadenas van a ser del tipo 1s1 donde s es cualquier cadena de ceros y unos, porque todos los números serán impares y porque la lista infinita de ceros antes del número no requiere ser representada. La operación entonces puede ser separada en tres elementos; la cabeza, el primer xor (que no lleva carry) y todo lo demás.
Sea z = 3*x, donde z y x son cadenas booleanas; z = z0,z1,z2,z3..., x = x0,x1,x2,x3,x4... Recordemos que las cadenas booleanas se leen de izquierda a derecha. Se da entonces que z0 = x0,x1,x2,x3... xor F,x0,x1,x2... xor F,F,c1,c2,c3...
XOR
V x1 x2 x3 x4 x5
F V x1 x2 x3 x4
c1 c2 c3 c4
-----------------
z0 z1 z2 z3 z4 z5el F (falso) es resultado de la "multiplicación por 2" de la cadena desplazada. Luego, tenemos tres casos. z0 será siempre verdadero y no producirá carry.
z1 será V xor x1 = -x1; xor con verdadero forma un inversor. La operación va a producir carry, aunque se puede calcular igual que el de z2 en adelante.
A partir de z2 es donde se complica el algoritmo. En principio z_n tiene el valor de x_n-1 xor x_n xor c_n-1, donde c_n-1 es el carry producido por la operación que generó a z_n-1.
¿Cómo calcular el carry, entonces? Veamos la tabla de verdad para x3, y su mapa K-V:
x1 x2 carry | x3 carry en x3 ----------------------------- F F F F F F F V V F F V F V F F V V F V V F F V F V F V F V V V F F V V V V V V Mapa KV x1,x2 \ 00 01 11 10 c 0 XXX 1 XXXXXXXXX
La reducción del mapa es (c y x1) o (c y x2) o (-c y x1 y x2) que se reduce aún más a "(c y (x1 o x2)) o (-c y (x1 y x2))"; en otras palabras, podemos ver cual era el carry de la operación anterior a la que estamos realizando, si era positivo utilizamos el operador 'o', si era negativo utilizamos el 'y', sobre las variables de la operación actual. Y, una vez que calculemos el carry de la operación actual, lo enviamos como argumento al constructor de la siguiente operación.
xor :: Bool -> Bool -> Bool xor = (/=) por_tres :: [Bool] -> [Bool] -- z0 = True por_tres (False:xs) = error "por_tres requiere impar" por_tres s = True : (primero s) where -- z1 = x0 XOR x1 = True XOR x1 = not x1 primero :: [Bool] -> [Bool] primero [] = error "por_tres: Sin datos" primero [True] = [True] -- (head t) es x1 primero (True:t) = (not (head t)) : (cola (True:t) False) -- z_n = x_n XOR x_n-1 XOR carry -- el Bool intermedio es el carry de la operación anterior cola :: [Bool] -> Bool -> [Bool] -- Caso final cola [False, False, False] _ = [] -- Traducción por chequeo de sanidad: -- menos de tres elementos cola [] p = cola [False, False, False] p cola [a] p = cola [a, False, False] p cola [a,b] p = cola [a, b, False] p -- Anamorfismo -- Al menos 3 elementos cola (h:n:t) prev = actual:siguiente where -- h es x_n-2, n es x_n-1, (head t) es x_n residuo = (carry h n prev) actual = (xor (xor n (head t)) residuo) siguiente = cola (n:t) residuo carry :: Bool -> Bool -> Bool -> Bool carry p q c = op [p,q] where op = if c then or else and
Ya con todas las operaciones se puede construir un evaluador:
bool_a_decimal :: [Bool] -> Integer -- La cadena vacía no es cero bool_a_decimal [] = error "Sin entrada" -- Catamorfismo bool_a_decimal s = foldl (\ x y -> if (fst y) then x + 2^(snd y) else x) 0 (zip s [0..]) -- Función tradicional, de enteros positivos impares a enteros positivos impares -- No suprayectiva (los múltiplos de 3 no tienen preimagen) -- No inyectiva (e.g. 1->1, 5->1) procesa :: Integer -> Integer procesa s = bool_a_decimal (mas_uno ( por_tres ( decimal_a_bool s ))) -- Anamorfismo de punto fijo "conocido" -- (si cicla es bueno, demostramos falsa la conjetura) a_uno :: Integer -> [Integer] a_uno 1 = [] a_uno x = (procesa x) : (a_uno (procesa x))
a_uno toma un entero y construye una lista de los impares intermedios entre el entero y 1 siguiendo las reglas de Collatz. No solamente es un algoritmo apreciablemente eficiente (falta analizarlo, pero se, uh, "siente" como orden lineal), sino que exhibe un resultado interesante: si se evalúa 'filter (\ x -> (snd x) > 99) (zip [3,5..65537] (map (length.a_uno) [3,5..65537]))' para ver cuantos impares entre 3 y 65537 requieren al menos 100 pasos (máximo 125) para llegar a 1, la longitud de la lista es de 67; los números son:
[13255,17647,17673,19593,19883,23529,26471,26511,26623,31419,
31687,34239,34719,35295,35347,35497,35655,37503,39009,39015,
39187,39707,39767,39935,40105,40959,42249,45055,45127,46443,
47059,47129,47329,47531,48927,49575,50815,51359,52011,52079,
52249,52507,52527,52943,53021,53247,53473,53483,56095,56255,
56487,56863,57115,59903,60073,60169,60231,60975,61439,61723,
61999,62745,62839,63105,63375,63387,64255]
Todos los demás convergen en menos de 100 operaciones. El método podría ser de utilidad en encontrar una función que acote superiormente el número de pasos requeridos para convergencia.
