Conjetura de Collatz

La conjetura de Collatz (o conjetura de Ulam), también conocida como problema 3n+1, establece que al aplicar el algoritmo 3n+1 a cualquier número entero positivo, este siempre terminará alcanzando el número 1.

La conjetura sigue sin demostrarse hasta el día de hoy: es simple de enunciar, pero extremadamente difícil de probar.

Tomar un número $ n $ (entero positivo no nulo), si $ n $ es par, dividirlo por $ 2 $, de lo contrario multiplicarlo por $ 3 $ y sumar $ 1 $. Repetir dando a $ n $ el valor del resultado previamente obtenido.

Matemáticamente, el algoritmo se define mediante la función $ f $ : $$ f_{3n+1}(n) = \begin{cases}{ \frac{n}{2}} & {\text{si }}n \equiv 0 \mod{2} \\ 3n+1 & {\text{si }} n \equiv 1 \mod{2} \end{cases} $$

Cuando se obtiene el valor $ 1 $, la secuencia generalmente se considera terminada, ya que el algoritmo entra en un bucle infinito de 4, 2, 1, 4, 2, 1, 4, 2, 1.

Si el número $ n $ es impar, entonces multiplicarlo por $ 3 $ y sumar $ 1 $ lo hace necesariamente par, por lo que el siguiente paso es obligatoriamente una división por 2.

La versión comprimida (o abreviada) fusiona los cálculos $ 3x+1 $ y $ x/2 $ en una sola etapa $ (3x+1)/2 $

Hasta la fecha, ningún número entero positivo contradice la conjetura de Siracusa.

Por eso la conjetura también se llama problema de Siracusa o problema de Collatz y no es un teorema.

Ha sido verificada por ordenador para miles de millones de valores, pero no existe ninguna demostración matemática general.

Encontrar un solo número que nunca llegue a $ 1 $ bastaría para demostrar que la conjetura es falsa.

La conjetura sigue sin demostrarse a pesar de decenas de pseudocientíficos que han afirmado tener una prueba.

En 2020, el matemático Terence Tao obtuvo un resultado parcial: mostró que la conjetura es verdadera para casi todos los enteros, en sentido probabilístico. Sin embargo, todavía no existe una demostración completa.

Un número nunca aparece 2 veces en la secuencia. (También es un problema abierto: demostrar que no existen bucles/ciclos)

Toda secuencia termina en una serie de potencias de 2.

Un número impar siempre es seguido por un número par.

Los números 5 y 32 generan la misma secuencia.

La conjetura puede escribirse en una sola expresión como $$ \frac{(7n + 2) - (5n + 2)(-1)^n}{4} $$ si $ n $ es par, entonces $ (-1)^n = 1 $, y $ \frac{(7n + 2) - (5n + 2)}{4} = \frac{2n}{4} = \frac{n}{2} $ y si $ n $ es impar, entonces $ (-1)^n = -1 $ y $ \frac{(7n + 2) + (5n + 2)}{4} = \frac{12n + 4}{4} = 3n + 1 $

Existen varias formas de programar un código fuente para el algoritmo:// Javascript
function step(n) {
if (n%2 == 0) return n/2;
return 3*n+1;
}
function collatz(n) {
var nb = 1;
while (n != 1) {
n = step(n);
nb++;
}
return nb;
}// Python
def collatz(n):
list = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
list.append(n)
return list

Otros nombres de la conjetura/problema de Collatz utilizados en la literatura son:

— conjetura de Siracusa

— conjetura de Ulam

— conjetura de Hailstone

— conjetura checa

— problema 3x+1 (o 3n+1)

— algoritmo de Hasse

— problema de Kakutani

— conjetura de Thwaite

El nombre de Siracusa provendría de la Universidad de Siracusa, una ciudad del estado de Nueva York en Estados Unidos, donde esta conjetura fue mencionada en los años 1950.

Esta tabla agrupa todos los números hasta 1000 en la forma (tiempo de vuelo/iteraciones => números que tienen ese tiempo de vuelo)

Esta tabla agrupa todos los números hasta 1000 en la forma (altitud máxima de vuelo => números que tienen esa altitud máxima)

La tabla anterior muestra altitudes de hasta 250504 para números hasta 1000. Pero existe una infinidad de números que llegan más alto.

Para cualquier número N dado (muy grande), el número impar más cercano a N tendrá una altitud aún mayor.

La conjetura fue formulada en 1937 por el matemático alemán Lothar Collatz.