Conjetura de Collatz

La conjetura de Collatz ^{[a] es uno de los} problemas sin resolver más famosos de las matemáticas . La conjetura pregunta si la repetición de dos operaciones aritméticas simples transformará eventualmente cada entero positivo en 1. Se refiere a secuencias de números enteros en las que cada término se obtiene del término anterior de la siguiente manera: si el término anterior es par , el siguiente término es la mitad del término anterior. Si el término anterior es impar, el siguiente término es 3 veces el término anterior más 1. La conjetura es que estas secuencias siempre llegan a 1, sin importar qué entero positivo se elija para comenzar la secuencia. Se ha demostrado que la conjetura es válida para todos los números enteros positivos hasta2,95 × 10 ²⁰ , pero no se ha encontrado ninguna prueba general.

Recibe su nombre en honor al matemático Lothar Collatz , quien introdujo la idea en 1937, dos años después de recibir su doctorado. ^[4] La secuencia de números involucrada a veces se conoce como secuencia de granizo, números de granizo o numerales de granizo (porque los valores suelen estar sujetos a múltiples descensos y ascensos como granizos en una nube), ^[5] o como números maravillosos. ^[6]

Paul Erdős dijo sobre la conjetura de Collatz: "Las matemáticas pueden no estar preparadas para este tipo de problemas". ^[7] Jeffrey Lagarias afirmó en 2010 que la conjetura de Collatz "es un problema extraordinariamente difícil, completamente fuera del alcance de las matemáticas actuales". ^[8] Sin embargo, aunque la conjetura de Collatz en sí sigue abierta, los esfuerzos por resolver el problema han conducido a nuevas técnicas y muchos resultados parciales. ^{[8] [9]}

Considere la siguiente operación sobre un entero positivo arbitrario :

• Si el número es par, divídelo por dos.
• Si el número es impar, triplícalo y súmalo uno.

En notación aritmética modular , defina la función f de la siguiente manera: $${\displaystyle f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

Ahora forme una secuencia realizando esta operación repetidamente, comenzando con cualquier entero positivo y tomando el resultado en cada paso como entrada en el siguiente.

En notación: (es decir: a _i es el valor de f aplicado a n recursivamente i veces; a _i = f ⁱ ( n ) ). $${\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}}$$ 

La conjetura de Collatz es: este proceso llegará finalmente al número 1, independientemente del entero positivo que se elija inicialmente. Es decir, para cada , hay algún con . ${\displaystyle n}$${\displaystyle i}$${\displaystyle a_{i}=1}$

Si la conjetura es falsa, sólo puede ser porque existe un número inicial que da lugar a una secuencia que no contiene el 1. Una secuencia de este tipo entraría en un ciclo repetitivo que excluye al 1, o bien aumentaría sin límite. No se ha encontrado ninguna secuencia de este tipo.

El i más pequeño tal que a _i < a ₀ se llama tiempo de parada de n . De manera similar, el k más pequeño tal que a _k = 1 se llama tiempo de parada total de n . ^[2] Si uno de los índices i o k no existe, decimos que el tiempo de parada o el tiempo de parada total, respectivamente, es infinito.

La conjetura de Collatz afirma que el tiempo total de parada de cada n es finito. También es equivalente a decir que cada n ≥ 2 tiene un tiempo de parada finito.

Dado que 3 n + 1 es par siempre que n sea impar, se puede utilizar en cambio la forma "abreviada" de la función Collatz: Esta definición produce valores más pequeños para el tiempo de detención y el tiempo de detención total sin cambiar la dinámica general del proceso. $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

Por ejemplo, comenzando con n = 12 y aplicando la función f sin "atajo", se obtiene la secuencia 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

El número n = 19 tarda más en llegar a 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

La secuencia para n = 27 , que aparece listada y graficada a continuación, toma 111 pasos (41 pasos a través de números impares, en negrita), subiendo 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, 03 , 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

(secuencia A008884 en la OEIS )

Los números con un tiempo de parada total mayor que el de cualquier valor inicial menor forman una secuencia que comienza con:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... (secuencia A006877 en la OEIS ).

Los valores de partida cuyo punto de trayectoria máximo es mayor que el de cualquier valor de partida menor son los siguientes:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (secuencia A006884 en la OEIS )

El número de pasos para que n llegue a 1 es

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (secuencia A006577 en la OEIS )

El valor inicial que tiene el mayor tiempo total de parada mientras está

menos de 10 es 9, que tiene 19 pasos,

menos de 100 es 97, que tiene 118 pasos,

menos de 1000 es 871, que tiene 178 pasos,

menos de 10 ⁴ es 6171, que tiene 261 pasos,

menos de 10 ⁵ es77 031 , que tiene 350 escalones,

menos de 10 ⁶ es837 799 , que tiene 524 pasos,

menos de 10 ⁷ es8 400 511 , que tiene 685 pasos,

menos de 10 ⁸ es63 728 127 , que tiene 949 pasos,

menos de 10 ⁹ es670 617 279 , que tiene 986 pasos,

menos de 10 ¹⁰ es9 780 657 630 , que tiene 1132 pasos, ^[10]

menos de 10 ¹¹ es75 128 138 247 , que tiene 1228 pasos,

menos de 10 ¹² es989 345 275 647 , que tiene 1348 pasos. ^[11] (secuencia A284668 en la OEIS )

Estos números son los más bajos con el recuento de pasos indicado, pero no necesariamente los únicos que están por debajo del límite indicado. A modo de ejemplo,9 780 657 631 tiene 1132 pasos, al igual que9 780 657 630 .

Los valores iniciales que tienen el menor tiempo total de parada con respecto a su número de dígitos (en base 2) son las potencias de dos, ya que 2 ⁿ se divide por la mitad n veces para llegar a 1, y nunca aumenta.

• 
  Gráfico dirigido que muestra las órbitas de los primeros 1000 números.
• 
  El eje x representa el número inicial, el eje y representa el número más alto alcanzado durante la cadena hasta 1. Este gráfico muestra un eje y restringido : algunos valores x producen valores intermedios tan altos como2,7 × 10 ⁷ (para x = 9663 )
• 
  El mismo gráfico que el anterior pero en escala logarítmica, por lo que se muestran todos los valores y . La primera línea gruesa hacia el medio del gráfico corresponde a la punta en 27, que alcanza un máximo en 9232.
• 
  El árbol de todos los números que tienen menos de 20 pasos.
• 
  El número de iteraciones que se necesitan para llegar a uno de los primeros 100 millones de números.

Aunque la conjetura no ha sido probada, la mayoría de los matemáticos que han estudiado el problema creen que es verdadera porque la evidencia experimental y los argumentos heurísticos la respaldan.

La conjetura ha sido comprobada por ordenador para todos los valores iniciales hasta 2 ⁶⁸ ≈2,95 × 10 ²⁰ . Todos los valores probados hasta ahora convergen a 1. ^[12]

Esta evidencia informática todavía no constituye una prueba rigurosa de que la conjetura sea verdadera para todos los valores iniciales, ya que se pueden encontrar contraejemplos al considerar números enteros positivos muy grandes (o posiblemente inmensos), como en el caso de las conjeturas de Pólya y de Mertens , que han sido refutadas .

Sin embargo, estas verificaciones pueden tener otras implicaciones. Ciertas restricciones de cualquier ciclo no trivial, como los límites inferiores de la longitud del ciclo, se pueden demostrar en función del valor del término más bajo del ciclo. Por lo tanto, las búsquedas por computadora para descartar ciclos que tengan un término más bajo pequeño pueden fortalecer estas restricciones. ^{[13] [14] [15]}

Si se consideran únicamente los números impares en la secuencia generada por el proceso de Collatz, entonces cada número impar es en promedio ⁠3/4⁠ del anterior. ^[16] (Más precisamente, la media geométrica de las proporciones de resultados es ⁠3/4⁠ .) Esto produce un argumento heurístico de que cada secuencia de Hailstone debería disminuir en el largo plazo, aunque esto no es evidencia en contra de otros ciclos, solo en contra de la divergencia. El argumento no es una prueba porque supone que las secuencias de Hailstone se ensamblan a partir de eventos probabilísticos no correlacionados. (Establece rigurosamente que la extensión 2-ádica del proceso de Collatz tiene dos pasos de división por cada paso de multiplicación para casi todos los valores iniciales 2-ádicos).

Como demostró Riho Terras , casi todos los números enteros positivos tienen un tiempo de parada finito. ^[17] En otras palabras, casi todas las secuencias de Collatz alcanzan un punto que está estrictamente por debajo de su valor inicial. La prueba se basa en la distribución de vectores de paridad y utiliza el teorema del límite central .

En 2019, Terence Tao mejoró este resultado al demostrar, utilizando la densidad logarítmica , que casi todas las órbitas de Collatz (en el sentido de densidad logarítmica) descienden por debajo de cualquier función dada del punto de partida, siempre que esta función diverja hasta el infinito, sin importar cuán lentamente lo haga. En respuesta a este trabajo, Quanta Magazine escribió que Tao "obtuvo uno de los resultados más significativos sobre la conjetura de Collatz en décadas". ^{[9] [18]}

En una prueba asistida por computadora , Krasikov y Lagarias demostraron que el número de números enteros en el intervalo [1, x ] que eventualmente llegan a 1 es al menos igual a x ^0,84 para todos los x suficientemente grandes . ^[19]

En esta parte, considere la forma abreviada de la función Collatz. Un ciclo es una secuencia ( a ₀ , a ₁ , ..., a _q ) de números enteros positivos distintos donde f ( a ₀ ) = a ₁ , f ( a ₁ ) = a ₂ , ..., y f ( a _q ) = a ₀ . $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

El único ciclo conocido es (1,2) de periodo 2, llamado ciclo trivial.

Se sabe que la longitud de un ciclo no trivial es al menos114 208 327 604 (o186 265 759 595 sin atajo). Si se puede demostrar que para todos los enteros positivos menores que las secuencias de Collatz llegan a 1, entonces este límite se elevaría a${\displaystyle 3\times 2^{69}}$217 976 794 617 (355 504 839 929 sin atajo). ^{[20] [14]} De hecho, Eliahou (1993) demostró que el período p de cualquier ciclo no trivial tiene la forma donde a , b y c son números enteros no negativos, b ≥ 1 y ac = 0 . Este resultado se basa en la expansión de fracción continua de ⁠$${\displaystyle p=301994a+17087915b+85137581c}$$en 3/en 2⁠ . ^[14]

Un k -ciclo es un ciclo que se puede dividir en k subsecuencias contiguas, cada una de las cuales consiste en una secuencia creciente de números impares, seguida de una secuencia decreciente de números pares. ^[15] Por ejemplo, si el ciclo consiste en una única secuencia creciente de números impares seguida de una secuencia decreciente de números pares, se denomina 1 -ciclo .

Steiner (1977) demostró que no existe ningún 1-ciclo aparte del trivial (1; 2) . ^[21] Simons (2005) utilizó el método de Steiner para demostrar que no existe ningún 2-ciclo. ^[22] Simons y de Weger (2005) ampliaron esta prueba hasta 68-ciclos; no existe ningún k -ciclo hasta k = 68. [ ^15] Hercher amplió el método aún más y demostró que no existe ningún k -ciclo con k ≤ 91. [ ^20] A medida que continúan las búsquedas exhaustivas por computadora, se pueden descartar valores k mayores . Para plantear el argumento de forma más intuitiva; no tenemos que buscar ciclos que tengan menos de 92 subsecuencias, donde cada subsecuencia consta de subidas consecutivas seguidas de bajadas consecutivas. ^{[ aclaración necesaria ]}

Existe otro enfoque para demostrar la conjetura, que considera el método de abajo hacia arriba para hacer crecer el llamado grafo de Collatz . El grafo de Collatz es un grafo definido por la relación inversa $${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n,{\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.}$$

Así, en lugar de demostrar que todos los números enteros positivos conducen finalmente a 1, podemos intentar demostrar que 1 conduce al revés a todos los números enteros positivos. Para cualquier número entero n , n ≡ 1 (mod 2) si y solo si 3 n + 1 ≡ 4 (mod 6) . De manera equivalente, ⁠n - 1/3⁠ ≡ 1 (mod 2) si y solo si n ≡ 4 (mod 6) . Conjeturalmente, esta relación inversa forma un árbol excepto por el bucle 1–2–4 (el inverso del bucle 4–2–1 de la función f inalterada definida en la sección Enunciado del problema de este artículo).

Cuando la relación 3 n + 1 de la función f se reemplaza por la relación de sustitución común "atajo "3n + 1/2⁠ , el gráfico de Collatz se define por la relación inversa, $${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1\\[4px]\left\{2n,{\frac {2n-1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.}$$

Para cualquier entero n , n ≡ 1 (mod 2) si y solo si ⁠3n + 1/2⁠ ≡ 2 (mod 3) . Equivalentemente, ⁠2n - 1/3⁠ ≡ 1 (mod 2) si y solo si n ≡ 2 (mod 3) . Conjeturalmente, esta relación inversa forma un árbol excepto por un bucle 1–2 (la inversa del bucle 1–2 de la función f(n) revisada como se indicó anteriormente).

Alternativamente, reemplace los 3 n + 1 con ⁠enano​/H ( n ′ )⁠ donde n ′ = 3 n + 1 y H ( n ′ ) es la potencia más alta de 2 que divide a n ′ (sin resto ). La función resultante f se asigna de números impares a números impares. Ahora supongamos que para algún número impar n , al aplicar esta operación k veces se obtiene el número 1 (es decir, f ^k ( n ) = 1 ). Entonces, en binario , el número n se puede escribir como la concatenación de cadenas w _k w _{k −1} ... w ₁ donde cada w _h es un extracto finito y contiguo de la representación de ⁠1/3 ^horas⁠ . ^[23] La representación de n, por tanto, contiene las repeticiones de ⁠1/3 ^horas⁠ , donde cada repetición se rota opcionalmente y luego se replica hasta un número finito de bits. Esto solo ocurre en binario. ^[24] Conjeturalmente, cada cadena binaria s que termina con un '1' se puede alcanzar mediante una representación de esta forma (donde podemos agregar o eliminar '0' iniciales a  s ).

Las aplicaciones repetidas de la función Collatz se pueden representar como una máquina abstracta que maneja cadenas de bits . La máquina realizará los siguientes tres pasos en cualquier número impar hasta que solo quede un 1 :

1. Añade 1 al final (derecho) del número en binario (dando 2 n + 1 );
2. Agregue esto al número original mediante la adición binaria (dando 2 n + 1 + n = 3 n + 1 );
3. Eliminar todos los 0 finales (es decir, dividir repetidamente por 2 hasta que el resultado sea impar).

El número inicial 7 se escribe en base dos como 111. La secuencia de Collatz resultante es:

         111
         111 1 
       1011 0 
      1011 1 
     10001 0 
    10001 1 
    1101 00 
   1101 1 
  101 000 
 101 1 
1 0000

Para esta sección, considere la forma abreviada de la función Collatz $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}.}$$

Si P(...) es la paridad de un número, es decir P(2 n ) = 0 y P(2 n + 1) = 1 , entonces podemos definir la secuencia de paridad de Collatz (o vector de paridad) para un número n como p _i = P( a _i ) , donde a ₀ = n , y a _{i +1} = f ( a _i ) .

¿Qué operación se realiza ?3n + 1/2⁠ o ⁠norte/2⁠ , depende de la paridad. La secuencia de paridad es la misma que la secuencia de operaciones.

Usando esta forma para f ( n ) , se puede demostrar que las secuencias de paridad para dos números m y n concordarán en los primeros k términos si y solo si m y n son equivalentes módulo 2 ^k . Esto implica que cada número se identifica de manera única por su secuencia de paridad y, además, que si hay múltiples ciclos de Hailstone, entonces sus ciclos de paridad correspondientes deben ser diferentes. ^{[2] [17]}

Al aplicar la función f k veces al número n = 2 ^k a + b se obtendrá el resultado 3 ^c a + d , donde d es el resultado de aplicar la función f k veces a b , y c es la cantidad de aumentos que se encontraron durante esa secuencia. Por ejemplo, para 2 ⁵ a + 1 hay 3 aumentos a medida que 1 itera a 2, 1, 2, 1 y, finalmente, a 2, por lo que el resultado es 3 ³ a + 2 ; para 2 ² a + 1 solo hay 1 aumento a medida que 1 aumenta a 2 y disminuye a 1, por lo que el resultado es 3 a + 1 . Cuando b es 2 ^k − 1 , entonces habrá k aumentos y el resultado será 3 ^k a + 3 ^k − 1 . La potencia de 3 multiplicada por a es independiente del valor de a ; depende solo del comportamiento de b . Esto permite predecir que ciertas formas de números siempre conducirán a un número menor después de una cierta cantidad de iteraciones: por ejemplo, 4 a + 1 se convierte en 3 a + 1 después de dos aplicaciones de f y 16 a + 3 se convierte en 9 a + 2 después de cuatro aplicaciones de f . Sin embargo, que esos números menores continúen hasta 1 depende del valor de a .

Para la función Collatz en forma abreviada

${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1.\end{cases}}{\pmod {2}}}$

Las secuencias de granizo se pueden calcular mediante el sistema de 2 etiquetas con reglas de producción

a → bc , b → a , c → aaa .

En este sistema, el entero positivo n se representa mediante una cadena de n copias de a , y la iteración de la operación de etiqueta se detiene en cualquier palabra de longitud menor a 2. (Adaptado de De Mol.)

La conjetura de Collatz establece de manera equivalente que este sistema de etiquetas, con una cadena finita arbitraria de a como palabra inicial, eventualmente se detiene (ver Sistema de etiquetas para un ejemplo resuelto).

Una extensión de la conjetura de Collatz es incluir todos los números enteros, no solo los positivos. Dejando de lado el ciclo 0 → 0, al que no se puede acceder desde fuera, hay un total de cuatro ciclos conocidos, en los que todos los números enteros distintos de cero parecen caer eventualmente bajo la iteración de f . Estos ciclos se enumeran aquí, comenzando con el ciclo bien conocido para  n positivo :

Los valores impares se muestran en negrita y grande. Cada ciclo se enumera con el miembro de menor valor absoluto (que siempre es impar) primero.

La conjetura de Collatz generalizada es la afirmación de que todo número entero, bajo iteración por f , eventualmente cae en uno de los cuatro ciclos anteriores o en el ciclo 0 → 0.

La función de Collatz se puede extender a números racionales (positivos o negativos) que tienen denominadores impares cuando se escriben en términos mínimos. El número se considera "impar" o "par" según si su numerador es par o impar. Entonces la fórmula para la función es exactamente la misma que cuando el dominio son los números enteros: un número racional "par" se divide por 2; un número racional "impar" se multiplica por 3 y luego se suma 1. Un hecho estrechamente relacionado es que la función de Collatz se extiende al anillo de números enteros 2-ádicos , que contiene el anillo de números racionales con denominadores impares como subanillo.

Al utilizar la definición "corta" del mapa de Collatz, se sabe que cualquier secuencia de paridad periódica es generada por exactamente un racional. ^[25] Por el contrario, se conjetura que cada racional con un denominador impar tiene una secuencia de paridad eventualmente cíclica (Conjetura de periodicidad ^[2] ).

Si un ciclo de paridad tiene una longitud n e incluye números impares exactamente m veces en índices k ₀ < ⋯ < k _{m −1} , entonces el único racional que genera inmediata y periódicamente este ciclo de paridad es

Por ejemplo, el ciclo de paridad (1 0 1 1 0 0 1) tiene una longitud de 7 y cuatro términos impares en los índices 0, 2, 3 y 6. Se genera repetidamente por la fracción , ya que esta última conduce al ciclo racional. $${\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}}$$$${\displaystyle {\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}.}$$

Cualquier permutación cíclica de (1 0 1 1 0 0 1) está asociada a una de las fracciones anteriores. Por ejemplo, el ciclo (0 1 1 0 0 1 1) se produce por la fracción $${\displaystyle {\frac {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {250}{47}}.}$$

Para una correspondencia uno a uno, un ciclo de paridad debe ser irreducible , es decir, no divisible en subciclos idénticos. Como ejemplo de esto, el ciclo de paridad (1 1 0 0 1 1 0 0) y su subciclo (1 1 0 0) están asociados a la misma fracción .5/7⁠ cuando se reduce a sus términos más bajos.

En este contexto, asumir la validez de la conjetura de Collatz implica que (1 0) y (0 1) son los únicos ciclos de paridad generados por números enteros positivos (1 y 2, respectivamente).

Si el denominador impar d de un racional no es múltiplo de 3, entonces todos los iterados tienen el mismo denominador y la secuencia de numeradores se puede obtener aplicando la  generalización " 3 n + d ^{" [26]} de la función de Collatz. $${\displaystyle T_{d}(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}},\\[4px]{\frac {3x+d}{2}}&{\text{if }}x\equiv 1{\pmod {2}}.\end{cases}}}$$

La función está bien definida en el anillo de números enteros 2-ádicos , donde es continua y preserva la medida con respecto a la medida 2-ádica. Además, se sabe que su dinámica es ergódica . ^[2]$${\displaystyle T(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}}\\[4px]{\frac {3x+1}{2}}&{\text{if }}x\equiv 1{\pmod {2}}\end{cases}}}$$${\displaystyle \mathbb {Z} _{2}}$

Defina la función del vector de paridad Q que actúa como ${\displaystyle \mathbb {Z} _{2}}$$${\displaystyle Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x)\mod 2\right)2^{k}.}$$

La función Q es una isometría 2-ádica . ^[27] En consecuencia, cada secuencia de paridad infinita ocurre exactamente para un entero 2-ádico, de modo que casi todas las trayectorias son acíclicas en . ${\displaystyle \mathbb {Z} _{2}}$

Una formulación equivalente de la conjetura de Collatz es que $${\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .}$$

El mapa de Collatz se puede extender a la línea real eligiendo cualquier función que evalúe cuando es un entero par, y o (para la versión "abreviada") cuando es un entero impar. Esto se llama función de interpolación . Una forma sencilla de hacerlo es elegir dos funciones y , donde: ${\displaystyle x/2}$${\displaystyle x}$${\displaystyle 3x+1}$${\displaystyle (3x+1)/2}$${\displaystyle x}$${\displaystyle g_{1}}$${\displaystyle g_{2}}$

${\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{ is even,}}\\0,&n{\text{ is odd,}}\end{cases}}}$

${\displaystyle g_{2}(n)={\begin{cases}0,&n{\text{ is even,}}\\1,&n{\text{ is odd,}}\end{cases}}}$

y usarlos como interruptores para nuestros valores deseados:

${\displaystyle f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)}$.

Una de esas opciones es y . Las iteraciones de este mapa conducen a un sistema dinámico , investigado más a fondo por Marc Chamberland. ^[28] Demostró que la conjetura no se cumple para números reales positivos ya que hay infinitos puntos fijos , así como órbitas que escapan monótonamente al infinito. La función tiene dos ciclos de atracción de período : y . Además, se conjetura que el conjunto de órbitas ilimitadas es de medida . ${\displaystyle g_{1}(x)\triangleq \cos ^{2}\left({\tfrac {\pi }{2}}x\right)}$${\displaystyle g_{2}(x)\triangleq \sin ^{2}\left({\tfrac {\pi }{2}}x\right)}$${\displaystyle f}$${\displaystyle 2}$${\displaystyle (1;\,2)}$${\displaystyle (1.1925...;\,2.1386...)}$ ${\displaystyle 0}$

Letherman, Schleicher y Wood extendieron el estudio al plano complejo . ^[29] Utilizaron la función de Chamberland para senos y cosenos complejos y agregaron el término adicional , donde es cualquier función completa . Dado que esta expresión se evalúa como cero para números enteros reales, la función extendida ${\displaystyle {\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+}$ ${\displaystyle h(z)\sin ^{2}(\pi z)}$${\displaystyle h(z)}$

${\displaystyle {\begin{aligned}f(z)\triangleq \;&{\frac {z}{2}}\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {3z+1}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right)\,+\\&{\frac {1}{\pi }}\left({\frac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)+h(z)\sin ^{2}(\pi z)\end{aligned}}}$

es una interpolación de la función de Collatz al plano complejo. La razón para agregar el término adicional es hacer que todos los enteros sean puntos críticos de . Con esto, muestran que ningún entero está en un dominio de Baker , lo que implica que cualquier entero es eventualmente periódico o pertenece a un dominio errante . Conjeturaron que esto último no es el caso, lo que haría que todas las órbitas de los enteros sean finitas. ${\displaystyle f}$

La mayoría de los puntos tienen órbitas que divergen hasta el infinito. Al colorear estos puntos en función de la velocidad a la que divergen se obtiene la imagen de la izquierda, para . Las regiones negras internas y la región externa son los componentes de Fatou , y el límite entre ellos es el conjunto de Julia de , que forma un patrón fractal , a veces llamado "fractal de Collatz". ${\displaystyle h(z)\triangleq 0}$${\displaystyle f}$

Hay muchas otras formas de definir una función de interpolación compleja, como utilizar la exponencial compleja en lugar de seno y coseno:

${\displaystyle f(z)\triangleq {\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)}$,

que presentan dinámicas diferentes. En este caso, por ejemplo, si , entonces . El conjunto de Julia correspondiente, que se muestra a la derecha, consta de un número incontable de curvas, llamadas pelos o rayos . ${\displaystyle \operatorname {Im} (z)\gg 1}$${\displaystyle f(z)\approx z+{\tfrac {1}{4}}}$

La sección Como secuencia de paridad anterior ofrece una forma de acelerar la simulación de la secuencia. Para adelantar k pasos en cada iteración (usando la función f de esa sección), divida el número actual en dos partes, b (los k bits menos significativos, interpretados como un entero) y a (el resto de los bits como un entero). El resultado de adelantar k pasos se da por

f ^k (2 ^k a + b ) = 3 ^{c ( b , k )} a + d ( b , k ) .

Los valores de c (o mejor 3 ^c ) y d se pueden precalcular para todos los posibles números de k bits b , donde d ( b , k ) es el resultado de aplicar la función f k veces a b , y c ( b , k ) es el número de números impares encontrados en el camino. ^[30] Por ejemplo, si k = 5 , uno puede saltar 5 pasos en cada iteración separando los 5 bits menos significativos de un número y usando

c (0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },

d (0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

Esto requiere un precomputación de 2 ^k y almacenamiento para acelerar el cálculo resultante en un factor de k , una compensación de espacio-tiempo .

Para el propósito especial de buscar un contraejemplo a la conjetura de Collatz, este precálculo conduce a una aceleración aún más importante, utilizada por Tomás Oliveira e Silva en sus confirmaciones computacionales de la conjetura de Collatz hasta valores grandes de  n . Si, para algunos b y k dados , la desigualdad

f ^k (2 ^k a + b ) = 3 ^{c ( b )} a + d ( b ) < 2 ^k a + b

se cumple para todo a , entonces el primer contraejemplo, si existe, no puede ser b módulo 2 ^k . ^[13] Por ejemplo, el primer contraejemplo debe ser impar porque f (2 n ) = n , menor que 2 n ; y debe ser 3 mod 4 porque f ² (4 n + 1) = 3 n + 1 , menor que 4 n + 1 . Para cada valor inicial a que no sea un contraejemplo de la conjetura de Collatz, hay un k para el cual se cumple dicha desigualdad, por lo que verificar la conjetura de Collatz para un valor inicial es tan bueno como verificar una clase de congruencia completa. A medida que k aumenta, la búsqueda solo necesita verificar aquellos residuos b que no son eliminados por valores menores de  k . Solo sobrevive una fracción exponencialmente pequeña de los residuos. ^[31] Por ejemplo, los únicos residuos supervivientes mod 32 son 7, 15, 27 y 31.

Los números enteros divisibles por 3 no pueden formar un ciclo, por lo que no es necesario comprobarlos como contraejemplos. ^[32]

Si k es un entero impar, entonces 3 k + 1 es par, por lo que 3 k + 1 = 2 ^a k ′ con k ′ impar y a ≥ 1 . La función de Siracusa es la función f del conjunto I de enteros impares positivos en sí misma, para la cual f ( k ) = k ′ (secuencia A075677 en la OEIS ).

Algunas propiedades de la función Siracusa son:

• Para todo k ∈ I , f (4 k + 1) = f ( k ) . (Porque 3(4 k + 1) + 1 = 12 k + 4 = 4(3 k + 1) .)
• En términos más generales: para todo p ≥ 1 y h impar , f ^{p − 1} (2 ^p h − 1) = 2 × 3 ^{p − 1} h − 1 . (Aquí f ^{p − 1} es la notación de iteración de función ).
• Para todos los h impares , f (2 h − 1) ≤ ⁠3 horas - 1/2⁠

La conjetura de Collatz es equivalente a la afirmación de que, para todo k en I , existe un entero n ≥ 1 tal que f ⁿ ( k ) = 1 .

En 1972, John Horton Conway demostró que una generalización natural del problema de Collatz es algorítmicamente indecidible . ^[33]

En concreto, consideró funciones de la forma donde a ₀ , b ₀ , ..., a _{P − 1} , b _{P − 1} son números racionales que se eligen de forma que g ( n ) sea siempre un entero. La función estándar de Collatz está dada por P = 2 , a ₀ = ⁠$${\displaystyle {g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},}$$1/2⁠ , b ₀ = 0 , a ₁ = 3 , b ₁ = 1 . Conway demostró que el problema

Dados g y n , ¿la secuencia de iteraciones g ^k ( n ) llega a 1 ?

es indecidible, al representar el problema de la detención de esta manera.

Más cercano al problema de Collatz está el siguiente problema cuantificado universalmente :

Dado g , ¿la secuencia de iteraciones g ^k ( n ) llega a 1 , para todo n > 0 ?

Modificar la condición de esta manera puede hacer que un problema sea más difícil o más fácil de resolver (intuitivamente, es más difícil justificar una respuesta positiva pero podría ser más fácil justificar una negativa). Kurtz y Simon ^[34] demostraron que el problema cuantificado universalmente es, de hecho, indecidible e incluso más alto en la jerarquía aritmética ; específicamente, es Π⁰
₂-completo. Este resultado de dureza se mantiene incluso si se restringe la clase de funciones g fijando el módulo P en 6480. ^[35]

Las iteraciones de g en una versión simplificada de esta forma, con todas iguales a cero, se formalizan en un lenguaje de programación esotérico llamado FRACTRAN . ${\displaystyle b_{i}}$

Collatz y otras conjeturas relacionadas se utilizan a menudo al estudiar la complejidad computacional. ^{[36] [37]} La ​​conexión se realiza a través de la función Busy Beaver , donde BB(n) es el número máximo de pasos dados por cualquier máquina de Turing de n estados que se detiene. Hay una máquina de Turing de 15 estados que se detiene si y solo si una conjetura de Paul Erdős (estrechamente relacionada con la conjetura de Collatz) es falsa. Por lo tanto, si se conociera BB(15), y esta máquina no se detuviera en ese número de pasos, se sabría que funciona para siempre y, por lo tanto, no existen contraejemplos (lo que prueba que la conjetura es verdadera). Esta es una forma completamente impráctica de resolver la conjetura; en cambio, se utiliza para sugerir que BB(15) será muy difícil de calcular, al menos tan difícil como resolver esta conjetura similar a Collatz.

• 3 x + 1 semigrupo
• Dinámica aritmética
• Aritmética modular
• Grupo afín por clase de residuo

• Matthews, Keith. "3 x + 1 página".
• Un proyecto de computación voluntaria en curso Archivado el 30 de agosto de 2021 en Wayback Machine por David Bařina verifica la convergencia de la conjetura de Collatz para valores grandes. (el mayor avance hasta ahora)
• ( BOINC ) proyecto de computación voluntaria Archivado el 4 de diciembre de 2017 en Wayback Machine que verifica la conjetura de Collatz para valores mayores.
• Un proyecto de computación voluntario en curso dirigido por Eric Roosendaal verifica la conjetura de Collatz para valores cada vez mayores.
• Otro proyecto de computación voluntaria en curso, a cargo de Tomás Oliveira e Silva, continúa verificando la conjetura de Collatz (con menos estadísticas que la página de Eric Roosendaal pero con mayores avances).
• Weisstein, Eric W. "Problema de Collatz". MundoMatemático .
• Problema de Collatz en PlanetMath ..
• Nochella, Jesse. "Caminos de Collatz". Proyecto de demostraciones de Wolfram .
• Eisenbud, D. (8 de agosto de 2016). ¿Indescifrable? La conjetura de Collatz (video corto). Numberphile. Archivado desde el original el 11 de diciembre de 2021 – vía YouTube.
• Eisenbud, D. (9 de agosto de 2016). ¿Indescifrable? Conjetura de Collatz (metraje adicional). Numberphile. Archivado desde el original el 11 de diciembre de 2021, vía YouTube.
• Alex Kontorovich (presentación) (30 de julio de 2021). El problema matemático más simple que nadie puede resolver (video corto). Veritasium – vía YouTube.
• ¿Están las computadoras preparadas para resolver este problema matemático notoriamente difícil de manejar?