Los vecinos de Collatz

En esta inusual entrada dominguera, toca otra vez un tema de matemáticas.

Hoy voy a hablar de los «vecinos» de la conjetura de Collatz, pero claro, antes de recorrer los alrededores de esta conjetura conviene introducir de qué va la misma.

Toma un número natural, el que quieras. Si es par, divídelo por 2 y si es impar, multiplícalo por 3 y agrégale 1. Toma el resultado y repite la operación anterior: esto dará una sucesión que puede representarse simbólicamente así

Esto es muy sencillo de programar, por lo que tampoco tienes que hacer todos los cálculos a mano. Por ejemplo, sabiendo que en Python puedes utilizar el operador % para calcular a_{n-1} \mod 2 (tienes una introducción chapucera a qué es esto de la «aritmética modular» en una reciente trilogía de artículos que comienza aquí), puedes utilizar una variante de este guion:

n = int(input("Ingrese el número inicial de la secuencia de Collatz: "))

def seq3np1(n):
    """ Muestra la secuencia 3n+1 para n,
        terminando cuando alcanza 1.
    """
    while n != 1:
        print(n, end=", ")
        if n % 2 == 0:          # n es par
            n = n // 2          # la doble barra es la división entera
        else:                   # n es impar
            n = n * 3 + 1
    print(n, end=".\n")

seq3np1(n)

Pues bien, la conjetura de Collatz nos dice que, tarde o temprano, siempre llegarás a 1.

Por ejemplo, si comenzamos por 5 el siguiente número será 3·5 + 1 = 16, el siguiente a este será 8, luego 4, 2 y llegamos al uno. Parte de cualquier número que se te ocurra, el proceso puede ser largo, pero siempre llegarás a uno… o al menos eso es lo que se cree, que por algo es todavía una conjetura.

Puede que tengas la impresión de que este algoritmo es un tanto arbitrario y quizás tengas razón. O no. Veamos, lo que estamos haciendo es que si un número es par, lo disminuimos a la mitad, mientras que si es impar lo hacemos más grande… pero atención, que esto es importe: también lo convertimos en un número par: el producto de dos números impartes (en este caso, a_{n-1} y 3) dará otro número impar, por lo que al sumar uno lo volvemos par. Y es que sin esta precaución la sucesión se nos iría rápidamente al demonio.

Ahora bien, y aquí comenzamos a explorar el vecindario de la conjetura, ¿por qué multiplicar por 3?, ¿por qué sumar uno? ¿Hay algo particular en estos números? Tal vez sí, tal vez no.

Hagamos algunas pruebas, supongamos que cuando a_{n-1} es impar (mantenemos el dividir por dos para los pares), en lugar de hacer lo que nos dice Collatz calculamos a_{n} = 5 \cdot a_{n-1} + 1, ¿qué obtenemos? Pues si partimos de 3, la secuencia será:

3 → 16 → 8 → 4 → 2 → 1

que parece bien, pero si partimos de 5,

5 → 26 → 13 → 66 → 33 → 166 → 83 → 416 → 208 → 104 → 52 → 26 → 13

y allí nos detenemos, ¡con el 26 hemos entrado en un bucle que jamás tocará el uno!

¿Y qué sucede si hacemos a_{n} = 3 \cdot a_{n-1} + 3? Pues que partiendo de 3

3 → 12 → 6 → 3

¡Otro bucle que no toca el 1!

Parecería que el 3 y el 1 que nos indica Collatz son importantes, después de todo. O quizás no, que por algo todo esto es todavía una conjetura.

¿Qué hay entonces de particular con el 3 y el 1? Pues nadie lo sabe. El tema está abierto a la espera de un matemático que encuentre una solución brillante. En una de esas, resolviendo esta conjetura se crean nuevas herramientas que producen una revolución en el campo de las matemáticas. O no, ¡quién sabe! Después de todo, es para saber que se hace investigación: como decía Gandalf, «ni aún el más sabio conoce el final de todos los caminos».