Conjetura de Collatz

La conjetura de Collatz, conocida también como conjetura 3n+1 o conjetura de Ulam (entre otros nombres), fue enunciada por el matemático Lothar Collatz en 1937, y aún no ha sido resuelta.

Enunciado

Tiempo de órbita (número de pasos o iteraciones) necesario para alcanzar la unidad para números comprendidos entre 1 y 13000.

Cota superior para valores entre 1 y 1300. La línea horizontal superior corresponde a la cota 9232. Esta cota es un valor 'preferido' para muchas secuencias, como las que comienzan con 27, 31, 41, 47, 54, 55, 62, 63, etc.

Sea la siguiente operación, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

Formalmente, esto equivale a una función $f:\mathbb {N} \mapsto \mathbb {N}$ :

$f(n)={\begin{cases}{\tfrac {n}{2}},&{\mbox{si }}n{\mbox{ es par}}\\3n+1,&{\mbox{si }}n{\mbox{ es impar}}\end{cases}}$

Ahora, se forma una sucesión mediante la aplicación de esta operación repetidamente, comenzando por cualquier entero positivo, y tomando el resultado de cada paso como la entrada del siguiente.

En notación:

a_{i}={\begin{cases}n&{\text{para }}i=0\\f(a_{i-1})&{\text{para }}i>0\end{cases}}

(esto es: $a_{i}$ es el valor de $f$ aplicado a $n$ recursivamente $i$ veces; $a_{i}=f^{i}(n)$ ).

La conjetura dice que siempre alcanzaremos el 1 independientemente del número con el que comencemos.

Ejemplos

Dado un número cualquiera, podemos considerar su órbita, es decir, las imágenes sucesivas al iterar la función. Por ejemplo, si n=13:

$f(13)=13\cdot 3+1=40$

$f(f(13))={\tfrac {40}{2}}=20$

$f(f(f(13)))={\tfrac {20}{2}}=10;\ {\mbox{etc.}}$

Si observamos este ejemplo, la órbita de 13 es periódica, es decir, se repite indefinidamente a partir de un momento dado, que corresponde con el ciclo 4, 2, 1:

13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Empezando en n = 6, la sucesión tiene 8 pasos, y llega a la siguiente sucesión: 6, 3, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 11, la sucesión tiene 14 pasos: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Empezando en n = 27, la sucesión tiene 111 pasos, llegando hasta 9232 antes de descender a 1: 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.
Empezando en n = 1002, la sucesión tiene 111 pasos, llegando hasta 9232 antes de descender a 1. Este caso es peculiar, ya que presenta algunas semejanzas con el número 27; como lo es que les toman 111 pasos llegar a 1, en el paso 77 llegan a su punto máximo, el cual es 9232 para ambas sucesiones.
Empezando en n = 75128138247, la sucesión tiene 1228 pasos para llegar a 1.
Empezando en n = 1424652103065, la sucesión tiene 1240 pasos para llegar a 1.
Empezando en n = 40523437598309, la sucesión tiene 1250 pasos para llegar a 1.
Empezando en n = 32018518596193, la sucesión tiene 1260 pasos para llegar a 1.
Empezando en n = 151791495567137, la sucesión tiene 1270 pasos para llegar a 1.
Empezando en n = 719604127133093, la sucesión tiene 1280 pasos para llegar a 1.
Empezando en n = 1705728301352515, la sucesión tiene 1289 pasos para llegar a 1.
Empezando en n = 16172831301712733, la sucesión tiene 1300 pasos para llegar a 1.

Estado actual del problema

Aunque no se ha demostrado la veracidad ni falsedad del resultado, existen ciertas evidencias en ambos sentidos.^{[cita requerida]}

Si existe algún contraejemplo a la conjetura (es decir, un número cuya secuencia no alcance nunca el 1), debe satisfacer alguna de estas condiciones:

la órbita del número no está acotada; o bien
la órbita también es periódica, pero con un período distinto de 4, 2, 1.

Evidencia computacional

Aunque formalmente no demuestra nada, existen diversos grupos de computación que se dedican a calcular las secuencias de números cada vez más grandes. En mayo de 2020 se comprobó la conjetura para todas las secuencias de números menores que $2^{68}$ .^[1]

Resultados parciales

Suma de potencias de 4

Los números que son suma de potencias de 4, como 5 = 1 + 4, 21 = 1 + 4 + 16, 85 = 1 + 4 + 16 + 64, 341 = 1 + 4 + 16 + 64 + 256, generan el 1 en forma casi directa, como en el ejemplo:

21 · 3 + 1 = 64, que es una potencia de 2 y genera el 1 al dividir 6 veces entre 2.

La prueba es muy simple:

$1+4+4^{2}+...+4^{n}$ es la suma de una progresión geométrica, e igual a $[4^{n}\cdot 4$ $-1]/3$ . Al aplicar el algoritmo, obtenemos una potencia de 4, que, luego de sucesivas divisiones entre 2 nos da 1.

Propiedades

Algunas propiedades de las trayectorias podrían ayudar a demostrar la conjetura. Las más importantes son las siguientes:

1) Las trayectorias de un número impar q y de 4q+1 se juntan. La demostración es muy simple también.

q -> 3q+1 4q+1 -> 12q + 4 -> 3q + 1 luego de dividir 12 q + 4 entre 2 dos veces.

2) Las trayectorias de un impar q y 2q+1 se unen en determinadas condiciones. Algunos ejemplos son 7 y 15, o 11 y 23. Si representamos sólo los impares, se ve este fenómeno más claramente.

7,11, 17, 13, 5, 1.

15,23, 35, 53, 5, 1.

Como se puede apreciar, 7 y 15 se juntan en el 5.

Nótese que 3 y 7 no se conectan de esa manera. 3, 5, 1

Un segundo ejemplo es el 11 y el 23.

11, 17, 13, 5, 1.

23, 35, 53, 5, 1.

11 no se conecta con el 5 de esta manera. 5, 1

Un tercer ejemplo es 27 y 55. Aquí vemos los primeros números y se juntan a nivel del 47

27, 41, 31, 47, 71, 107,...

55, 83, 125, 47, 71, 107, ...

Esta propiedad funciona para la gran mayoría de los números.

Números que terminan en 3

Al agregar un 3 al final a estos números (a partir del 1, el 13, a partir del 5, el 53, a partir del 21, el 213, a partir del 85, el 853, etc), se obtiene 5, a partir del cual se obtiene 1.

213 = 210 + 3

213 · 3 + 1 = 639 + 1 = 640 = 5 · 128

128 es una potencia de 2, por lo que, dividiendo 7 veces entre 2, se llega a 1

Se puede generalizar este resultado de la siguiente manera: Si $x$ es un impar, y $(3x+1)/$ $2^{k}$ es otro impar, llamémosle $p$ , al aplicar el algoritmo de Collatz a $x$ , el siguiente impar será $5p$ .

Ejemplos: 3 -> 10 -> 5. El siguiente impar en la sucesión del 3 es el 5. Entonces, el siguiente impar en la sucesión del 33 será el 25 = $5\cdot 5$ .

7-> 22 -> 11. El siguiente impar en la sucesión del 7 es el 11. Entonces, el siguiente impar en la sucesión del 73 será el 55 = $11\cdot 5$ .

Potencias de 4 más uno

Los números que son de la forma $4^{n}+1$ generan $3^{n}+1$ y estos son menores que el número de partida para todo n natural.

3 mod 6

Los números que son de la forma 3 mod 6 pueden considerarse como generadores de números mayores. Por ejemplo, el 31 puede generarse partiendo del 27. De la misma forma, el 111 genera el 334 que pertenece a la sucesión de números que empieza en el 27.

Patrones

Patrón binario

Se ha propuesto el estudio de patrones en sistema binario para el estudio de las propiedades de los números expresados como polinomios de potencias de 2, lo que simplifica el estudio de las propiedades de los mismos. Luego pueden ser demostrados los teoremas correspondientes. Por ejemplo, los números como 5, 21, 85, etc., tienen una expresión del tipo 10101...01 en sistema binario. Esos números son, entonces, los coeficientes de un polinomio en potencias pares de 2.

$3\cdot \left(2^{0}+2^{2}+...+\left(2^{n}\right)^{2}\right)+1=4\cdot 4^{n}$

Los números del tipo 111...11 (n unos) que son iguales a $2^{n}-1$ , generan en un primer momento los de este tipo: 1011...111, (n+1 cifras). En un segundo momento se obtiene 10001...1 (n+2 cifras), luego 11010111...1, etc.

Variantes

Existen algunas variantes como, por ejemplo, la conjetura 2n+2, la cual se enuncia exactamente igual cambiando la función de impares a pares, es decir, si el número es impar, se multiplica por 2 y se suma 2.

Código

Un posible código en python a esta conjetura para demostrarla es la siguiente:

# Definir una función que aplica la operación de la conjetura
def collatz(n):
  if n % 2 == 0: # Si el número es par, se divide entre 2
    return n // 2
  else: # Si el número es impar, se multiplica por 3 y se suma 1
    return 3 * n + 1

# Pedir al usuario que ingrese un número entero positivo
n = int(input("Ingrese un número entero positivo: "))

# Mientras el número no sea 1, aplicar la función y mostrar el resultado
while n != 1:
  n = collatz(n)
  print(n)

Como otra opcion, en Rust puede demostrarse con este código:

use std::io;//esto es necesario para leer la entrada de la terminal

fn collazt(mut n: u32) -> (usize, Vec<u32>) {
    let mut iteraciones: Vec<u32> = Vec::new();//esta variable almacena las iteraciones de la funcion
    println!("Collazt. Parametro inicial: {n}");
    while n > 1 {
        n = if n % 2 == 0 { n / 2 } else { n * 3 + 1 };//aqui se aplica la formula
        iteraciones.push(n);//esta funcion introduce el valor de n en las iteraciones
    }
    return (iteraciones.len(), iteraciones);//regresa la cantidad de pasos y las iteraciones
}

fn main() {
    loop {
        println!("Ingrese un numero entero positivo:");
        let mut input_line = String::new();//esta variable guardara la entrada
        io::stdin().read_line(&mut input_line).expect("Error al leer entrada");//esto lee la linea
        if let Ok(x) = input_line.trim().parse::<u32>(){//convierte a numero positivo entero
            let coll = collazt(x);//ejecuta la funcion y guarda los valores que regresa
            println!("numero de pasos: {}. Secuencia: {:?}", coll.0, coll.1);//muestra los valores
            }
        else {println!("La entrada no era un numero entero positivo")}//si la entrada no es correcta, se mostrara este mensaje en lugar de lo anterior
        println!()
    }
}

Referencias

↑ Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x

Enlaces externos

Wikilibros alberga un libro o manual sobre Implementaciones de la conjetura de Collatz.
Información actualizada sobre cálculos (en inglés)
Web de un investigador que busca una demostración (en inglés)
Artículo de revisión sobre el tema (en inglés)
Método recursivo del algoritmo en PHP
Implementación del algoritmo en PHP
Proyecto BOINC, que usa el poder de cálculo de las GPU´s (Ati, Nvidia) y de CPU, para encontrar la solución a este problema Archivado el 4 de diciembre de 2017 en Wayback Machine. (en inglés)
Ponencia presentada en el 43 Congreso de la Sociedad Matemática Mexicana; Tuxtla Gutiérrez, Chiapas 2010
También puede interesar "Las Metaprogresiones de las Secuencias de Collatz" en https://www.researchgate.net/publication/317010660_LAS_METAPROGRESIONES_DE_LAS_SECUENCIAS_DE_COLLATZ_Ideas_Preliminares_Para_Una_Formalizacion_ACTUALIZACION
Establece una relación entre los conjuntos infinitos resultantes de la aplicación del algoritmo de Collatz y el conjunto resultante de la progresión geométrica que crece en razón de 2n desde el valor inicial 1 al infinito (2n;1,∞)
La conjetura de Collatz y otros agujeros negros matemáticos
Collatz en Excel

Datos: Q837314
Multimedia: Collatz conjecture / Q837314

[1] Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x

[1]