La conjetura de Collatz es uno de esos problemas matemáticos que son muy fáciles de enunciar pero que encierran una complejidad maravillosa.
No es la primera vez que me enfrento a este problema, es un clásico como ejercicio para cualquier lenguaje de programación, pero en esta ocasión usaré Python que es mi favorito últimamente.
Tabla de contenidos
Conjetura de Collatz
Pero primero lo primero ¿Qué es la conjetura de Collatz?
Empezamos con un número entero positivo. Lo evaluamos, si el número es par entonces lo dividimos entre 2. Si es impar, entonces se multiplica por 3 y se le suma 1. Al resultado lo volvemos a evaluar y nuevamente aplicamos las operaciones correspondientes.
Al final, la secuencia de números termina con 4 , 2, 1
Pero esto no se ha demostrado que ocurra en todos los números enteros positivos, por eso es una conjetura.
Veamos un ejemplo muy simple:
numero = int(input("Teclee un número entero positivo : "))
if numero > 0:
while numero != 1:
if numero % 2:
numero = numero * 3 + 1
else:
numero //= 2
print(numero)
else:
print("El número que tecleo no es válido")Un detalle curioso es como se evalúa si un número es par o impar.
numero % 2
Como pueden ver, se utiliza el operador módulo % que regresa el residuo de dividir el número entre 2.
Si el residuo es cero, entonces es par, si es uno entonces es impar.
En el if de una forma prácticamente directa evaluamos si es par o impar.
Ahora veamos el resultado:
Teclee un número entero positivo : 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
La ejecución del programa se detiene cuando el valor de numero llega a 1.
Ahora en modo recursivo.
La recursión es una forma muy interesante de atacar un problema. Porque para llegar a la solución se llama nuevamente a la misma función.
Si tiene curiosidad haga una pausa y declare una función que haga las operaciones y podrá entender el ejercicio mental que es declarar una función recursiva.
El peligro es la condición de salida, porque si no se cumple, el programa puede entrar en un bucle infinito y no queremos eso.
numero = int(input("Teclee un número entero positivo : "))
def collatz(numero):
print(numero)
while numero != 1:
if numero % 2:
return collatz(numero * 3 + 1)
else:
return collatz(numero // 2)
if numero > 0:
collatz(numero)
else:
print("El número que tecleo no es válido")
Todavía tengo sentimientos encontrados sobre la ubicación de la instrucción print(numero) , si son observadores notarán la diferencia.
Teclee un número entero positivo : 11 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Pero para lo único que la necesito es para «ver» el comportamiento de la variable numero durante la ejecución del programa.
Haciendo Pruebas
¿Ahora que sigue? esto lo voy a hacer como ejercicio personal. Voy a poner todos los resultados intermedios en una variable que sea una lista para mostrarla al final. Y probablemente haré un test que comprobará los resultados.
Doctest
Pues al final no me quedé con las ganas e incluí algunas pruebas dentro del código. En Python hay varias formas, pero me decidí por la que considero la más integrada y más sencilla para mí doctest. Las pruebas se integran perfectamente a manera de comentarios con datos de entrada y el resultado que se espera.
Este es el código que incluye las pruebas:
def collatz(n):
"""
Regresa en una lista los valores de una serie de Collatz
>>> collatz(11)
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
>>> collatz(12)
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
>>> collatz(27)
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
"""
resultado = []
resultado.append(n)
while n != 1:
if n % 2:
n = n * 3 + 1
else:
n //= 2
resultado.append(n)
return resultado
numero = int(input("Teclee un número entero positivo : "))
if numero > 0:
print(collatz(numero))
else:
print("El número que tecleo no es válido")
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=False)El código se ejecuta de manera normal, así que para invocar las pruebas se hace de la siguiente forma.
python -m doctest -v collatz.py
Teclee un número entero positivo : 7
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Trying:
collatz(11)
Expecting:
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
ok
Trying:
collatz(12)
Expecting:
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
ok
Trying:
collatz(27)
Expecting:
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
ok
1 items had no tests:
collatz
1 items passed all tests:
3 tests in collatz.collatz
3 tests in 2 items.
3 passed and 0 failed.
Test passed.Con esto logró dos objetivos pendientes. Almacenar el resultado en una lista y las pruebas del código.
El tema de la Conjetura de Collatz es fascinante, pero no soy un divulgador así que si quieren saber más del tema les recomiendo este video.
Sientanse libres de comentar el código, de esta forma se exploran nuevos enfoques que uno no conoce.
¡Saludos y hasta el próximo código!