¿La secuencia de Collatz finalmente llega a 1 para todos los valores iniciales enteros positivos?
La conjetura de Collatz es una conjetura en matemáticas que concierne a secuencias definidas de la siguiente manera: comience con cualquier número entero positivo n . Entonces cada término se obtiene del término anterior de la siguiente manera: si el término anterior es par , el término siguiente 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 no importa qué valor de n , la secuencia siempre llegará a 1.
La conjetura lleva el nombre de Lothar Collatz , quien introdujo la idea en 1937, dos años después de recibir su doctorado. [1] También se conoce como el 3 n + 1 problema , la 3 n + 1 conjetura , la conjetura Ulam (después de Stanisław Ulam ), el problema de Kakutani (después de Shizuo Kakutani ), la conjetura Thwaites (después Sir Bryan Thwaites ), Hasse de algoritmo (después de Helmut Hasse ), o el problema de Siracusa . [2] [4] La secuencia de números involucrados a veces se denomina secuencia de granizo o números de granizo (porque los valores generalmente están sujetos a múltiples descensos y ascensos como granizo en una nube), [5] [6] o como maravilloso números . [7]
Paul Erdős dijo sobre la conjetura de Collatz: "Es posible que las matemáticas no estén preparadas para tales problemas". [8] También ofreció 500 dólares estadounidenses por su solución. [9] Jeffrey Lagarias declaró en 2010 que la conjetura de Collatz "es un problema extraordinariamente difícil, completamente fuera del alcance de las matemáticas actuales". [10]
Planteamiento del problema
Considere la siguiente operación en un entero positivo arbitrario :
- Si el número es par, divídelo por dos.
- Si el número es impar, triplícalo y suma uno.
En notación aritmética modular , defina la función f de la siguiente manera:
Ahora forme una secuencia realizando esta operación repetidamente, comenzando con cualquier número 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 an recursivamente i veces; a i = f i ( n ) ).
La conjetura de Collatz es: Este proceso eventualmente alcanzará el número 1, independientemente del número entero positivo que se elija inicialmente.
Si la conjetura es falsa, solo puede ser porque hay algún número inicial que da lugar a una secuencia que no contiene 1. Tal secuencia entraría en un ciclo repetido que excluye 1, o aumentaría sin límite. No se ha encontrado tal secuencia.
El i más pequeño tal que a i < a 0 se denomina tiempo de parada de n . De manera similar, el menor k tal que a k = 1 se denomina tiempo total de parada de n . [3] Si uno de los índices i o k no existe, decimos que el tiempo de parada o el tiempo total de parada, 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 es impar, en su lugar se puede usar la forma de "atajo" de la función Collatz
Datos empiricos
Por ejemplo, comenzando con n = 12 , 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 1: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 , enumerada 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, 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 (secuencia A008884 en la OEIS )
Los números con un tiempo de parada total mayor que el de cualquier valor inicial más pequeño 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 iniciales cuyo punto de trayectoria máximo es mayor que el de cualquier valor inicial 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 son
- 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 se
- 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 4 es 6171, que tiene 261 pasos,
- menos de 10 5 es 77 031 , que tiene 350 pasos,
- menos de 10 6 es 837 799 , que tiene 524 pasos,
- menos de 10 7 es 8 400 511 , que tiene 685 pasos,
- menos de 10 8 es 63 728 127 , que tiene 949 pasos,
- menos de 10 9 es 670 617 279 , que tiene 986 escalones,
- menos de 10 10 es 9 780 657 630 , que tiene 1132 pasos, [11]
- menos de 10 11 es 75 128 138 247 , que tiene 1228 pasos,
- menos de 10 12 es 989 345 275 647 , que tiene 1348 pasos,
- menos de 10 13 es 7 887 663 552 367 , que tiene 1563 pasos,
- menos de 10 14 es 80 867 137 596 217 , que tiene 1662 pasos,
- menos de 10 15 es 942 488 749 153 153 , que tiene 1862 pasos,
- menos de 10 16 es 7 579 309 213 675 935 , que tiene 1958 pasos,
- menos de 10 17 es 93 571 393 692 802 302 , que tiene 2091 pasos y
- menos de 10 18 es 931 386 509 544 713 451 , que tiene 2283 pasos. [12]
Estos números son los más bajos con el recuento de pasos indicado, pero no necesariamente los únicos por debajo del límite dado. Como ejemplo,9 780 657 631 tiene 1132 pasos, como lo hace9 780 657 630 .
Los valores iniciales que tienen el tiempo de parada total más pequeño con respecto a su número de dígitos (en base 2) son las potencias de dos, ya que 2 n se reduce a la mitad n veces para llegar a 1, y nunca se incrementa.
Visualizaciones
Gráfico dirigido que muestra las órbitas de los primeros 1000 números.
El árbol de todos los números tiene menos de 20 pasos (haga clic para ampliar) .
Argumentos de apoyo
Aunque la conjetura no ha sido probada, la mayoría de los matemáticos que han investigado el problema piensan que la conjetura es cierta porque la evidencia experimental y los argumentos heurísticos la apoyan.
Evidencia experimental
A partir de 2020[actualizar], la conjetura ha sido verificada por computadora para todos los valores iniciales hasta 2 68 ≈ 2.95 × 10 20 . Todos los valores iniciales probados hasta ahora terminan eventualmente en el ciclo repetitivo (4; 2; 1) del período 3. [13]
Esta evidencia informática no es suficiente para demostrar que la conjetura es cierta para todos los valores iniciales. Como en el caso de algunas conjeturas refutadas, como la conjetura de Pólya , se pueden encontrar contraejemplos al considerar números muy grandes.
Sin embargo, estas verificaciones pueden tener otras implicaciones. Por ejemplo, se pueden derivar restricciones adicionales sobre el período y la forma estructural de un ciclo no trivial . [14] [15] [16]
Una heurística probabilística
Si se consideran solo los números impares en la secuencia generada por el proceso de Collatz, entonces cada número impar está en promedio3/4del anterior. [17] (Más precisamente, la media geométrica de las razones de los resultados es 3/4.) Esto produce un argumento heurístico de que cada secuencia de Hailstone debería disminuir a largo plazo, aunque esto no es una evidencia contra otros ciclos, solo contra 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 Collatz tiene dos pasos de división para cada paso de multiplicación para casi todos los valores iniciales 2-ádicos).
Tiempos de parada
Como lo demostró Terras, casi todo entero positivo n tiene un tiempo de parada finito. [18] En otras palabras, casi todas las secuencias de Collatz alcanzan un punto que está estrictamente por debajo de su valor inicial. La demostración se basa en la distribución de vectores de paridad y utiliza el teorema del límite central .
En 2019, Terence Tao mejoró considerablemente este resultado al mostrar, usando densidad logarítmica , que casi todas las órbitas de Collatz están descendiendo por debajo de cualquier función dada del punto de partida, siempre que esta función diverja al infinito, no importa cuán lentamente. En respuesta a este trabajo, Quanta Magazine escribió que Tao "obtuvo uno de los resultados más significativos de la conjetura de Collatz en décadas". [19] [20]
Límites inferiores
En una demostración asistida por computadora , Krasikov y Lagarias demostraron que el número de enteros en el intervalo [1, x ] que eventualmente llegan a 1 es al menos igual ax 0,84 para todo x suficientemente grande . [21]
Ciclos
En esta parte, considere la forma de acceso directo de la función Collatz
Un ciclo es una secuencia ( a 0 , a 1 , ..., a q ) de enteros positivos distintos donde f ( a 0 ) = a 1 , f ( a 1 ) = a 2 , ..., y f ( a q ) = un 0 .
El único ciclo conocido es (1, 2) del período 2, llamado ciclo trivial.
Duración del ciclo
Se sabe que la duración de un ciclo no trivial es al menos 17 087 915 . [15] De hecho, Eliahou (1993) demostró que el período p de cualquier ciclo no trivial es de la forma
donde una , b y c son números enteros no negativos, b ≥ 1 y ac = 0 . Este resultado se basa en la expansión continua de la fracción deEn 3/En 2.
Un razonamiento similar que da cuenta de la reciente verificación de la conjetura de hasta 2 68 conduce a la cota inferior mejorado114 208 327 604 (o186 265 759 595 sin el "atajo"). Este límite inferior es consistente con el resultado anterior, ya que114 208 327 604 =17 087 915 × 361 +85 137 581 ×1269 .
k -ciclos
Un k- ciclo es un ciclo que se puede dividir en 2 k subsecuencias contiguas: k secuencias crecientes de números impares alternadas con k secuencias decrecientes de números pares. [16] Por ejemplo, si el ciclo consta de una única secuencia creciente de números impares seguida de una secuencia decreciente de números pares, se denomina ciclo 1 .
Steiner (1977) demostró que no existe un ciclo más que el trivial (1; 2) . [22] Simons (2004) utilizó el método de Steiner para demostrar que no hay 2 ciclos. [23] Simons y de Weger (2005) ampliaron esta prueba hasta 68 ciclos: no hay k- ciclo hasta k = 68 . [16] Para cada k más allá de 68, este método da un límite superior para el término más pequeño de un ciclo k : por ejemplo, si hay un ciclo de 77, entonces al menos un elemento del ciclo es menor que 38137 × 2 50 . [16] Junto con la verificación de la conjetura de hasta 2 68 , esto implica la no existencia de un no trivial k -ciclo hasta k = 77 . [13] A medida que continúan las búsquedas exhaustivas por computadora, se pueden descartar valores de k más grandes . Para exponer el argumento de manera más intuitiva: no necesitamos buscar ciclos que tengan como máximo 77 circuitos, donde cada circuito consiste en subidas consecutivas seguidas de bajadas consecutivas.
Otras formulaciones de la conjetura
En reversa
Hay otro enfoque para probar la conjetura, que considera el método ascendente de crecimiento del llamado gráfico de Collatz . El gráfico de Collatz es un gráfico definido por la relación inversa
Entonces, en lugar de probar que todos los enteros positivos eventualmente conducen a 1, podemos intentar demostrar que 1 conduce hacia atrás a todos los enteros positivos. Para cualquier número entero n , n ≡ 1 (mod 2) si y solo si 3 n + 1 ≡ 4 (mod 6) . Equivalentemente,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 ciclo 1–2–4 (el inverso del ciclo 4–2–1 de la función inalterada f 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 sustitutiva común "atajo"3 n + 1/2, el gráfico de Collatz se define por la relación inversa,
Para cualquier número entero n , n ≡ 1 (mod 2) si y solo si3 n + 1/2≡ 2 (mod 3) . Equivalentemente,2 n - 1/3≡ 1 (mod 2) si y solo si n ≡ 2 (mod 3) . Conjeturalmente, esta relación inversa forma un árbol excepto por un ciclo 1–2 (el inverso del ciclo 1–2 de la función f (n) revisada como se indicó anteriormente).
Alternativamente, reemplace el 3 n + 1 conn ′/H ( n ′)donde n ′ = 3 n + 1 y H ( n ′) es la potencia más alta de 2 que divide n ′ (sin resto ). La función resultante f mapea de números impares a números impares. Ahora suponga que para algún número impar n , aplicar esta operación k veces da como resultado el número 1 (es decir, f k ( n ) = 1 ). Luego, en binario , el número n se puede escribir como la concatenación de cadenas w k w k −1 ... w 1 donde cada w h es un extracto finito y contiguo de la representación de1/3 h. [24] Por tanto, la representación de n contiene las repeticiones de1/3 h, donde cada repetición se rota opcionalmente y luego se replica hasta un número finito de bits. Es solo en binario que esto ocurre. [25] Conjeturalmente, cada cadena binaria s que termina con un '1' puede ser alcanzada por una representación de esta forma (donde podemos agregar o eliminar los '0's iniciales a s ).
Como una máquina abstracta que calcula en base dos
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":
- Agregue 1 al final (derecho) del número en binario (dando 2 n + 1 );
- Suma esto al número original mediante la suma binaria (dando 2 n + 1 + n = 3 n + 1 );
- Elimine todos los "0" finales (es decir, divida repetidamente por dos hasta que el resultado sea impar).
Ejemplo
El número inicial 7 se escribe en base dos como 111. La secuencia de Collatz resultante es:
111 111 1 1 01101 011 1 10 001010 001 1 1101001101 1 101000101 1 10000
Como secuencia de paridad
Para esta sección, considere la función Collatz en la forma ligeramente modificada
Esto se puede hacer porque cuando n es impar, 3 n + 1 siempre es par.
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 0 = n , y a i +1 = f ( a i ) .
Qué operación se realiza, 3 n + 1/2 o norte/2, depende de la paridad. La secuencia de paridad es la misma que la secuencia de operaciones.
Usando esta forma de f ( n ) , se puede demostrar que las secuencias de paridad para dos números m y n estarán de acuerdo en los primeros k términos si y sólo si m y n son equivalentes modulo 2 k . Esto implica que cada número se identifica de forma única por su secuencia de paridad y, además, si hay varios ciclos de Hailstone, sus ciclos de paridad correspondientes deben ser diferentes. [3] [18]
Aplicar la función f k veces al número n = 2 k a + b dará el resultado 3 c a + d , donde d es el resultado de aplicar la función f k veces ab , yc es cuántos aumentos se encontraron durante esa secuencia (por ejemplo, para 2 5 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 3 a + 2 ; para 2 2 a + 1 solo hay 1 aumenta a medida que 1 sube a 2 y cae a 1, por lo que el resultado es 3 a + 1 ). Cuando b es 2 k - 1 , habrá k aumentos y el resultado será 2 × 3 k a - 1 . El factor de 3 multiplicando 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 más pequeño después de un cierto número 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 4 aplicaciones de f . Sin embargo, si esos números más pequeños continúan a 1, depende del valor de a .
Como sistema de etiquetas
Para la función Collatz en la forma
Las secuencias de granizo se pueden calcular mediante el sistema extremadamente simple de 2 etiquetas con reglas de producción
- a → bc , b → a , c → aaa .
En este sistema, el entero positivo n está representado por 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 que 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 # Ejemplo: Cálculo de secuencias de Collatz para un ejemplo resuelto).
Extensiones a dominios más grandes
Iterando en todos los enteros
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 que no se puede ingresar desde el exterior, hay un total de 4 ciclos conocidos, en los que todos los enteros distintos de cero parecen caer eventualmente bajo la iteración de f . Estos ciclos se enumeran aquí, comenzando con el ciclo conocido para n positivo :
Los valores impares se enumeran en negrita grande. Cada ciclo se enumera con su miembro de menor valor absoluto (que siempre es impar) primero.
Ciclo | Duración del ciclo de valor impar | Duración del ciclo completo |
---|---|---|
1 → 4 → 2 → 1 ... | 1 | 3 |
−1 → −2 → −1 ... | 1 | 2 |
−5 → −14 → −7 → −20 → −10 → −5 ... | 2 | 5 |
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ... | 7 | 18 |
La conjetura generalizada de Collatz es la afirmación de que cada entero, bajo iteración por f , eventualmente cae en uno de los cuatro ciclos anteriores o el ciclo 0 → 0. El ciclo 0 → 0 a menudo se considera "trivial" por el argumento, ya que solo se incluye por razones de integridad.
Iterando en racionales con denominadores impares
El mapa 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 toma como 'impar' o 'par' según si su numerador es par o impar. Entonces, la fórmula para el mapa es exactamente la misma que cuando el dominio son los números enteros: un "par" tal racional se divide por 2; un 'impar' tal racional se multiplica por 3 y luego se suma 1. Un hecho estrechamente relacionado es que el mapa de Collatz se extiende al anillo de enteros 2-ádicos , que contiene el anillo de racionales con denominadores impares como un subanillo.
Cuando se utiliza la definición de "atajo" del mapa de Collatz, se sabe que cualquier secuencia de paridad periódica es generada por exactamente un racional. [26] A la inversa, se conjetura que todo racional con un denominador impar tiene una secuencia de paridad eventualmente cíclica (Conjetura de periodicidad [3] ).
Si un ciclo de paridad tiene una longitud n e incluye números impares exactamente m veces en índices k 0 <⋯ < k m −1 , entonces el único racional que genera inmediata y periódicamente este ciclo de paridad es
( 1 )
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. Es generado repetidamente por la fracción
ya que este último conduce al ciclo racional
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) es producido por la fracción
Para una correspondencia uno a uno, un ciclo de paridad debería ser irreducible , es decir, no dividirse en subciclos idénticos. Como ilustración 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 los 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 todas las iteraciones tienen el mismo denominador y la secuencia de numeradores se puede obtener aplicando la generalización " 3 n + d " [27] de la función de Collatz.
Extensión 2-ádica
La función
está bien definido en el anillo ℤ 2 de enteros 2-ádicos , donde es continuo y conserva la medida con respecto a la medida 2-ádica. Además, se sabe que su dinámica es ergódica . [3]
Defina la función de vector de paridad Q actuando sobre ℤ 2 como
- .
La función Q es una isometría 2-ádica . [28] 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.
Una formulación equivalente de la conjetura de Collatz es que
Iterando en números reales o complejos
El mapa de Collatz (con acceso directo) se puede ver como la restricción a los números enteros del mapa suave.
Las iteraciones de este mapa en la línea real conducen a un sistema dinámico , investigado más a fondo por Chamberland. [29] Mostró que la conjetura no es válida para los 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 del período 2, y . Además, se conjetura que el conjunto de órbitas ilimitadas es de medida 0.
Letherman, Schleicher y Wood ampliaron el estudio al plano complejo , donde la mayoría de los puntos tienen órbitas que divergen hasta el infinito (región coloreada en la ilustración). [30] El límite entre la región coloreada y los componentes negros , es decir, el conjunto de Julia de, es un patrón fractal , a veces llamado el "fractal Collatz".
Optimizaciones
Compensación tiempo-espacio
La sección anterior Como secuencia de paridad ofrece una forma de acelerar la simulación de la secuencia. Para avanzar 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 número entero) y a (el resto de los bits como un número entero). El resultado de saltar k pasos adelante se puede encontrar como:
- f k (2 k un + b ) = 3 c ( b ) un + d ( b ) .
Las matrices c (o mejor 3 c ) yd se calculan previamente para todos los números de k bits posibles b , donde d ( b ) es el resultado de aplicar la función f k veces ab , yc ( b ) es el número de números impares. números encontrados en el camino. [31] Por ejemplo, si k = 5 , uno puede avanzar 5 pasos en cada iteración separando los 5 bits menos significativos de un número y usando:
- c (0 ... 31) = {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) = {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 2 k precomputation y almacenamiento para acelerar el cálculo resultante por un factor de k , una solución de compromiso espacio-tiempo .
Restricciones modulares
Con el propósito especial de buscar un contraejemplo a la conjetura de Collatz, esta precomputación 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, por alguna dado b y k , la desigualdad
- f k (2 k un + b ) = 3 c ( b ) un + d ( b ) <2 k un + b
se cumple para todo a , entonces el primer contraejemplo, si existe, no puede ser b módulo 2 k . [14] 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 2 (4 n + 1) = 3 n + 1 , menor que 4 n + 1 . Para cada valor inicial a que no es un contraejemplo de la conjetura de Collatz, existe una k para la 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 más bajos de k . Solo sobrevive una fracción exponencialmente pequeña de los residuos. [32] Por ejemplo, los únicos residuos supervivientes mod 32 son 7, 15, 27 y 31.
Función de Siracusa
Si k es un número entero impar, entonces 3 k + 1 es par, entonces 3 k + 1 = 2 a k ′ con k ′ impar y a ≥ 1 . La función Siracusa es la función f del conjunto I de enteros impares en sí mismo, para los cuales f ( k ) = k ′ (secuencia A075677 en la OEIS ).
Algunas propiedades de la función Syracuse 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 más generalidad: 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 impares h , f (2 h - 1) ≤ 3 h - 1/2
La conjetura de Collatz es equivalente a la afirmación de que, para todo k en I , existe un número entero n ≥ 1 tal que f n ( k ) = 1 .
Generalizaciones indecidibles
En 1972, John Horton Conway demostró que una generalización natural del problema de Collatz es algorítmicamente indecidible . [33]
Específicamente, consideró funciones de la forma
y a 0 , b 0 , ..., a P - 1 , b P - 1 son números racionales que se eligen de modo que g ( n ) sea siempre un número entero.
La función estándar de Collatz viene dada por P = 2 , a 0 = 1/2, b 0 = 0 , a 1 = 3 , b 1 = 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 cerca del 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 anterior es, de hecho, indecidible e incluso superior en la jerarquía aritmética , específicamente Π0
2-completo. Este resultado de dureza se mantiene incluso si se restringe la clase de funciones g fijando el módulo P en 6480. [35]
En la cultura popular
En la película Incendies , un estudiante de posgrado en matemáticas puras explica la conjetura de Collatz a un grupo de estudiantes. Pone sus estudios en espera por un tiempo para abordar algunas preguntas sin resolver sobre el pasado de su familia. Al final de la película, la conjetura de Collatz resulta haber presagiado un descubrimiento inquietante y difícil que hace sobre su familia. [36] [37]
Ver también
- 3 x + 1 semigrupo
- Dinámica aritmética
- Aritmética modular
- Grupo afín de clase de residuo
Otras lecturas
- El desafío definitivo: el problema 3 x + 1 :
- Este volumen, [10] editado por Jeffrey Lagarias y publicado por la American Mathematical Society , es un compendio de información sobre la conjetura de Collatz, métodos para abordarla y generalizaciones. Incluye dos trabajos de encuesta del editor y cinco de otros autores, sobre la historia del problema, generalizaciones, enfoques estadísticos y resultados de la teoría de la computación . También incluye reimpresiones de los primeros trabajos sobre el tema (incluida una entrada de Lothar Collatz).
Referencias
- ^ O'Connor, JJ; Robertson, EF (2006). "Lothar Collatz" . Escuela de Matemáticas y Estadística de la Universidad de St Andrews, Escocia.
- ^ Maddux, Cleborne D .; Johnson, D. Lamont (1997). Logotipo: una retrospectiva . Nueva York: Haworth Press. pag. 160. ISBN 0-7890-0374-0.
El problema también se conoce con varios otros nombres, que incluyen: la conjetura de Ulam, el problema de Hailstone, el problema de Syracuse, el problema de Kakutani, el algoritmo de Hasse y el problema de Collatz.
- ^ a b c d e f g Lagarias, Jeffrey C. (1985). "El problema 3 x + 1 y sus generalizaciones". The American Mathematical Monthly . 92 (1): 3–23. doi : 10.1080 / 00029890.1985.11971528 . JSTOR 2322189 .
- ↑ Según Lagarias (1985), [3] p. 4, el nombre "Problema de Siracusa" fue propuesto por Hasse en la década de 1950, durante una visita a la Universidad de Siracusa .
- ^ Pickover, Clifford A. (2001). Maravillas de los números . Oxford: Prensa de la Universidad de Oxford. pp. 116 -118. ISBN 0-19-513342-0.
- ^ "Número de granizo" . MathWorld . Wolfram Research.
- ^ Hofstadter, Douglas R. (1979). Gödel, Escher, Bach . Nueva York: Basic Books. págs. 400-2 . ISBN 0-465-02685-0.
- ^ Guy, Richard K. (2004). " " E17: Secuencias de permutación " " . Problemas no resueltos en teoría de números (3ª ed.). Springer-Verlag . págs. 336–7. ISBN 0-387-20860-7. Zbl 1058.11001 .
- ^ Guy, RK (1983). "No intentes solucionar estos problemas". Amer. Matemáticas. Mensual . 90 (1): 35–41. doi : 10.2307 / 2975688 . JSTOR 2975688 . Con esto Erdos quiere decir que no existen herramientas poderosas para manipular tales objetos.
- ^ a b Lagarias, Jeffrey C. , ed. (2010). El desafío definitivo: el problema 3 x + 1 . Sociedad Matemática Estadounidense . ISBN 978-0-8218-4940-8. Zbl 1253.11003 .
- ^ Leavens, Gary T .; Vermeulen, Mike (diciembre de 1992). " Programas de búsqueda 3 x + 1". Computadoras y Matemáticas con Aplicaciones . 24 (11): 79–99. doi : 10.1016 / 0898-1221 (92) 90034-F .
- ^ Roosendaal, Eric. "Registros con retardo 3x + 1" . Consultado el 14 de marzo de 2020 . (Nota: los "registros de demora" son registros de tiempo total de parada).
- ^ a b Barina, David (2020). "Verificación de la convergencia del problema de Collatz". El diario de la supercomputación . 77 (3): 2681–2688. doi : 10.1007 / s11227-020-03368-x . S2CID 220294340 .
- ^ a b Garner, Lynn E. (1981). "Sobre el algoritmo Collatz 3 n + 1". Actas de la American Mathematical Society . 82 (1): 19-22. doi : 10.2307 / 2044308 . JSTOR 2044308 .
- ^ a b Eliahou, Shalom (1993). "El problema de 3 x + 1: nuevos límites inferiores en longitudes de ciclo no triviales". Matemáticas discretas . 118 (1): 45–56. doi : 10.1016 / 0012-365X (93) 90052-U .
- ^ a b c d Simons, J .; de Weger, B. (2005). " Límites teóricos y computacionales para m -ciclos del problema 3 n + 1" (PDF) . Acta Arithmetica . 117 (1): 51–70. Código bibliográfico : 2005AcAri.117 ... 51S . doi : 10.4064 / aa117-1-3 .
- ^ Lagarias (1985), [3] sección " Un argumento heurístico" .
- ^ a b Terras, Riho (1976). "Un problema de tiempo de parada en los enteros positivos" (PDF) . Acta Arithmetica . 30 (3): 241–252. doi : 10.4064 / aa-30-3-241-252 . Señor 0568274 .
- ^ Tao, Terence (10 de septiembre de 2019). "Casi todas las órbitas de Collatz alcanzan valores casi acotados" . ¿Qué hay de nuevo ? Consultado el 11 de septiembre de 2019 .
- ^ Hartnett, Kevin. "El matemático demuestra un gran resultado en el problema 'peligroso'" . Revista Quanta . Consultado el 26 de diciembre de 2019 .
- ^ Krasikov, Ilia; Lagarias, Jeffrey C. (2003). "Límites para el problema 3 x + 1 usando desigualdades en diferencias" . Acta Arithmetica . 109 (3): 237–258. arXiv : matemáticas / 0205002 . Código Bibliográfico : 2003AcAri.109..237K . doi : 10.4064 / aa109-3-4 . Señor 1980260 . S2CID 18467460 .
- ^ Steiner, RP (1977). "Un teorema sobre el problema de Siracusa". Actas de la 7ma Conferencia de Manitoba sobre Matemáticas Numéricas . págs. 553–9. Señor 0535032 .
- ^ Simons, John L. (2005). "Sobre la inexistencia de 2 ciclos para el problema 3 x + 1" . Matemáticas. Comp . 74 : 1565–72. Código Bibliográfico : 2005MaCom..74.1565S . doi : 10.1090 / s0025-5718-04-01728-4 . Señor 2137019 .
- ^ Colussi, Livio (9 de septiembre de 2011). "Las clases de convergencia de la función Collatz" . Informática Teórica . 412 (39): 5409–5419. doi : 10.1016 / j.tcs.2011.05.056 .
- ^ Hew, Patrick Chisan (7 de marzo de 2016). "Trabajar en binario protege las repeticiones de 1/3 h : comentario sobre 'Las clases de convergencia de la función Collatz ' de Colussi " . Informática Teórica . 618 : 135-141. doi : 10.1016 / j.tcs.2015.12.033 .
- ^ Lagarias, Jeffrey (1990). "El conjunto de ciclos racionales para el problema 3x + 1" . Acta Arithmetica . 56 (1): 33–53. doi : 10.4064 / aa-56-1-33-53 . ISSN 0065-1036 .
- ^ Belaga, Edward G .; Mignotte, Maurice (1998). "Incorporación de la conjetura 3x + 1 en un contexto 3x + d" . Matemáticas experimentales . 7 (2): 145-151. doi : 10.1080 / 10586458.1998.10504364 .
- ^ Lagarias, Jeffrey C .; Bernstein, Daniel J. (1996). "El mapa conjugado 3 x + 1". Revista Canadiense de Matemáticas . 48 (6): 1154-1169. doi : 10.4153 / CJM-1996-060-x . ISSN 0008-414X .
- ^ Chamberland, Marc (1996). "Una extensión continua del problema 3 x + 1 a la línea real". Dynam. Contin. Sistemas de impulsos discretos . 2 (4): 495–509.
- ^ Letherman, Simon; Schleicher, Dierk; Madera, Reg (1999). "El (3 n + 1) -Problema y dinámica holomorfa". Matemáticas experimentales . 8 (3): 241–252. doi : 10.1080 / 10586458.1999.10504402 .
- ^ Scollo, Giuseppe (2007). "Buscando Récords de Clase en el Problema 3 x + 1 mediante la Infraestructura Grid COMETA" (PDF) . Jornadas de puertas abiertas en la Universidad de Palermo .
- ↑ Lagarias (1985), [3] Teorema D.
- ^ Conway, John H. (1972). "Iteraciones impredecibles". Proc. 1972 Conf. Teoría de Números, Univ. Colorado, Boulder . págs. 49–52.
- ^ Kurtz, Stuart A .; Simon, Janos (2007). "La indecidibilidad del problema de Collatz generalizado" . En Cai, J.-Y .; Cooper, SB; Zhu, H. (eds.). Actas de la 4ta Conferencia Internacional sobre Teoría y Aplicaciones de Modelos de Computación, TAMC 2007, celebrada en Shanghai, China en mayo de 2007 . págs. 542–553. doi : 10.1007 / 978-3-540-72504-6_49 . ISBN 978-3-540-72503-9.Como PDF
- ^ Ben-Amram, Amir M. (2015). "Mortalidad de funciones afines por partes iteradas sobre los enteros: Decidibilidad y complejidad". Computabilidad . 1 (1): 19–56. doi : 10.3233 / COM-150032 .
- ^ Emmer, Michele (2012). Imagine Math: Between Culture and Mathematics . Springer Publishing . págs. 260–264. ISBN 978-8-847-02426-7.
- ^ Mazmanian, Adam (19 de mayo de 2011). "RESEÑA DE LA PELÍCULA: 'Incendies ' " . The Washington Times . Consultado el 7 de diciembre de 2019 .
enlaces externos
- Página 3 x + 1 de Keith Matthews : Revisión del progreso, además de varios programas .
- Proyecto de computación distribuida ( BOINC ) que verifica la conjetura de Collatz para valores mayores.
- Un continuo de computación distribuida proyecto de Eric Roosendaal verifica la conjetura de Collatz para valores más grandes y más grandes.
- Otro en curso de computación distribuida proyecto de Tomás Oliveira e Silva sigue verificando la conjetura de Collatz (con un menor número de estadísticas que la página de Eric Roosendaal, pero con los nuevos progresos realizados).
- Weisstein, Eric W. "Problema de Collatz" . MathWorld .
- Problema de Collatz en PlanetMath ..
- Nochella, Jesse. "Caminos de Collatz" . Proyecto de demostraciones Wolfram .
- Los matemáticos están tan cerca de resolver este acertijo de 82 años