Conjetura de Collatz

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Problema abierto en funciones 3x+1 y x/2

Problema no resuelto en matemáticas:

¿La secuencia de Collatz finalmente alcanza 1 para todos los valores iniciales enteros positivos?

(Problemas más no resueltos en matemáticas)

Gráfico dirigido que muestra las órbitas de pequeños números bajo el mapa de Collatz, saltando incluso números. La conjetura de Collatz afirma que todos los caminos eventualmente conducen a 1.

La conjetura de Collatz es uno de los problemas matemáticos sin resolver más famosos. La conjetura pregunta si la repetición de dos operaciones aritméticas simples eventualmente transformará cada número entero positivo en 1. Se trata de 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 de el 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.

Lleva el nombre del matemático Lothar Collatz, quien introdujo la idea en 1937, dos años después de recibir su doctorado. También se conoce como el problema $3 n + 1$ , el $3 n + 1$ conjetura, la conjetura de Ulam (después de Stanisław Ulam), problema de Kakutani (después de Shizuo Kakutani), la conjetura de Thwaites (después de Sir Bryan Thwaites), el algoritmo de Hasse (después de Helmut Hasse), o el problema de Syracuse. La secuencia de números involucrados a veces se denomina secuencia de granizo, números de granizo o números de granizo (porque los valores suelen estar sujetos a múltiples descendencias). y asciende como granizo en una nube), o como números maravillosos.

Paul Erdős dijo acerca de la conjetura de Collatz: "Las matemáticas pueden no estar preparadas para tales problemas". También ofreció US$500 por su solución. 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".

Enunciado del problema

Números de 1 a 9999 y su tiempo total de parada correspondiente

Histograma de tiempos de parada total para los números 1 a 10⁸. El tiempo total de parada es en

x

axis, frecuencia en el

Sí.

Axis.

Histograma de tiempos de parada total para los números 1 a 10⁹. El tiempo total de parada es en

x

axis, frecuencia en el

Sí.

Axis.

Tiempo de publicación para entradas de 2 a 10⁷.

Tiempo de parada total hasta 250, 1000, 4000, 20000, 100000, 500000

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

Si el número es incluso, dividirlo por dos.
Si el número es extraño, triple y añadir uno.

En notación aritmética modular, defina la función $f$ de la siguiente manera:

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

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:

0end{cases}}}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">ai={}nparai=0f()ai− − 1)parai■0{displaystyle a_{i}={begin{cases}n {fnMicrosoft Sans Serif}0end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f00de0e2db28328fcc982c27c17eb4a578624778" style="vertical-align: -2.505ex; width:25.593ex; height:6.176ex;"/>

a i

f

n

i

a i = f i () n)

La conjetura de Collatz es: Este proceso finalmente alcanzará el número 1, independientemente del entero positivo que se elija inicialmente.

Si la conjetura es falsa, solo puede deberse a que hay un número inicial que da lugar a una secuencia que no contiene 1. Tal secuencia entraría en un ciclo repetitivo que excluye 1 o aumentaría sin límite. No se ha encontrado tal secuencia.

La menor $i$ tal que $a i < a 0$ se llama el tiempo de parada de $n$ . Del mismo modo, la menor $k$ tal que $a k = 1$ se llama el tiempo de parada total de $n$ . 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 de parada total de cada $n$ es finito. También es equivalente a decir que todo $n \geq 2$ tiene un tiempo de parada finito.

Dado que $3 n + 1$ es par siempre que $n$ es extraño, en su lugar se puede usar el "atajo" forma de la función de Collatz:

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

Datos empíricos

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 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 como alto como 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 el 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,... A006877 en el OEIS).

Los valores iniciales cuyo punto de trayectoria máximo es mayor que 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 el OEIS)

Número de pasos para $n$ para llegar a 1 son

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

El valor inicial que tiene el mayor tiempo de parada total 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⁴ es 6171, que tiene 261 pasos,

menos de 10⁵ es 77031, que tiene 350 pasos,

menos de 10⁶ es 837799, que tiene 524 pasos,

menos de 10⁷ es 8400511, que tiene 685 pasos,

menos de 10⁸ es 63728127, que tiene 949 pasos,

menos de 10⁹ es 670617279, que tiene 986 pasos,

menos de 10¹⁰ es 9780657630, que tiene 1132 pasos,

menos de 10¹¹ es 75128138247, que tiene 1228 pasos,

menos de 10¹² es 989345275647, que tiene 1348 pasos.

Estos números son los más bajos con el conteo de pasos indicado, pero no necesariamente los únicos por debajo del límite dado. Como ejemplo, 9780657631 tiene 1132 pasos, al igual que 9780657630.

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

Visualizaciones

Gráfico dirigido que muestra las órbitas de los primeros 1000 números.
El $x$ axis representa el número de inicio, el $Sí.$ axis representa el mayor número alcanzado durante la cadena a 1. Esta parcela muestra una restricción $Sí.$ axis: algunos $x$ valores producen intermediarios tan altos como 2.7×10⁷ (por $x = 9663$ )
La misma parcela a la izquierda pero a escala de troncos, así que todo $Sí.$ se muestran los valores. La primera línea gruesa hacia el centro de la parcela corresponde a la punta a 27, que alcanza un máximo a 4616.
El árbol de todos los números tiene menos de 20 pasos.
El número de iteraciones que se necesita para llegar a uno para los primeros 100 millones de números.

Argumentos de apoyo

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

Evidencia experimental

A partir de 2020, la conjetura ha sido verificada por computadora para todos los valores iniciales hasta 2⁶⁸ ≈ 2,95×10²⁰. Todos los valores iniciales probados hasta ahora finalmente terminan en el ciclo repetitivo $(4; 2; 1)$ del período 3.

Esta evidencia informática aún no es 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 la conjetura refutada de Pólya.

Sin embargo, tales 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.

Una heurística probabilística

Si uno considera solo 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. (Más precisamente, la media geométrica de las proporciones de los resultados es 3 //span>4.) Esto produce un argumento heurístico de que cada secuencia de Hailstone debería disminuir a largo plazo, aunque esto no es 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 de 2 ádicos del proceso de Collatz tiene dos pasos de división para cada paso de multiplicación para casi todos los valores iniciales de 2 ádicos).

Tiempos de parada

Como lo demostró Riho Terras, casi todos los números enteros positivos tienen un tiempo de finalización finito. En otras palabras, casi todas las secuencias de Collatz alcanzan un punto 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ó este resultado al mostrar, utilizando densidad logarítmica, que casi todas las órbitas de Collatz 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. 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".

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 a $x 0.84$ para todos los $x$ .

Ciclos

En esta parte, considere la forma abreviada de la función Collatz

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

() a 0, a 1,... a q)

f () a 0) a 1

f () a 1) a 2

f () a q) a 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 17087915. De hecho, Eliahou (1993) demostró que el período $p$ de cualquier ciclo no trivial es de la forma

{displaystyle p=301994a+17087915b+85137581c}

a

b

c

b \geq 1

ac = 0

3 / In 2

K-ciclos

Un ciclo $k$ es un ciclo que se puede dividir en $2 k$ subsecuencias contiguas: $k$ secuencias crecientes de números impares que alternan con $k$ secuencias decrecientes de números pares. 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 1 ciclo.

Steiner (1977) demostró que no existe un ciclo único aparte del trivial $(1; 2)$ . Simons (2005) utilizó el método de Steiner para probar que no hay 2 ciclos. Simons &amperio; de Weger (2005) amplió esta prueba hasta 68 ciclos: no hay $k$ -cycle hasta $k = 68$ . Para cada $k$ más allá de 68, este método proporciona un límite superior para el término más pequeño de un $k$ -cycle: por ejemplo, si hay un ciclo de 77, entonces al menos un elemento del ciclo es menor que 38137×2⁵⁰. Junto con la verificación de la conjetura hasta $268$ , esto implica la inexistencia de un $k$ -ciclo hasta $k = 77$ . A medida que continúan las búsquedas informáticas exhaustivas, es posible que se descarten valores mayores de $k$ . Para exponer el argumento de manera más intuitiva: no necesitamos buscar ciclos que tengan como máximo 77 circuitos, donde cada circuito consta de subidas consecutivas seguidas de bajadas consecutivas.

Otras formulaciones de la conjetura

Al revés

Los primeros 21 niveles de Gráfico de Collatz generado en la moda de abajo arriba. El gráfico incluye todos los números con una longitud de órbita de 21 o menos.

Hay otro enfoque para probar la conjetura, que considera el análisis de abajo hacia arriba método de crecimiento del llamado gráfico de Collatz. El gráfico de Collatz es un gráfico definido por la relación inversa

{displaystyle R(n)={begin{cases}{2n}&{text{if }}nequiv 0,1,2,3,5\[4px]left{2n,{frac {n-1}{3}}right}&{text{if }}nequiv 4end{cases}}{pmod {6}}.}

Entonces, en lugar de probar que todos los números enteros positivos eventualmente conducen a 1, podemos intentar probar que 1 conduce hacia atrás a todos los números enteros positivos. Para cualquier número entero $n$ , $n \equiv 1 (mod 2)$ si y solo si $3 n + 1 \equiv 4 (mod 6)$ . De manera equivalente, $n - 1 / 3 \equiv 1 (mod 2)$ si y solo si $n \equiv 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 inalterada $f$ definido en la sección Declaración del problema de este artículo).

Cuando la relación $3 n + 1$ de la función $f$ se reemplaza por el sustituto común "atajo" relación $3 n + 1 / 2$ , el gráfico de Collatz se define por la relación inversa,

{displaystyle R(n)={begin{cases}{2n}&{text{if }}nequiv 0,1\[4px]left{2n,{frac {2n-1}{3}}right}&{text{if }}nequiv 2end{cases}}{pmod {3}}.}

Para cualquier entero $n$ , $n \equiv 1 (mod 2)$ si y solo si $3 n + 1 / 2 \equiv 2 (mod 3)$ . De manera equivalente, $2 n - 1 / 3 \equiv 1 (mod 2)$ si y solo si <span class="texhtml" n ≡ 2 (mod 3). Conjeturalmente, esta relación inversa forma un árbol excepto por un bucle 1–2 (el inverso del bucle 1–2 de la función f(n) revisada como se indicó anteriormente).

Como alternativa, reemplace el $3 n + 1$ con $n' / H (n')$ donde $n' = 3 n + 1$ y $H (n')$ es la máxima potencia de 2 que divide a $n'$ (sin resto). La función resultante $f$ asigna números impares a números impares. Supongamos ahora que para algún número impar $n$ , aplicando 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 de $1 / 3 h$ . La representación de $n$ por lo tanto contiene los repetidos de $1 / 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. Conjeturalmente, cada cadena binaria $s$ que termina con '1' se puede llegar mediante una representación de este formulario (donde podemos agregar o eliminar '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:

Apéndice 1 hasta el final (derecho) del número en binario (dar $2 n + 1$ );
Añadir esto al número original por adición binaria (dar $2 n + 1 + n = 3 n + 1$ );
Quitar todos los rastros 0s (es decir, dividir repetidamente por 2 hasta que el resultado es extraño).

Ejemplo

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

 111
 111110110 10111100010 100011110100 11011101000 101110000

Como una secuencia de paridad

Para esta sección, considere la función de Collatz en la forma ligeramente modificada

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

Esto se puede hacer porque cuando $n$ es impar, $3 n + 1$ siempre es par.

Si $P(...)$ es la paridad de un número, eso es $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 $n / 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 la secuencia de paridad para dos números $m$ y $n$ estarán de acuerdo en los primeros $k$ términos si y solo si $m$ y $n$ son módulos equivalentes $2 k$ . Esto implica que cada número se identifica de manera única por su secuencia de paridad y, además, si hay varios ciclos de Hailstone, entonces sus ciclos de paridad correspondientes deben ser diferentes.

Aplicando la función $f$ $k$ multiplicado por el número $n = 2 k a + b$ dará el resultado $3 c a + d$ , donde $d$ es el resultado de aplicar $f$ función $k$ veces a $b$ , y $c$ es cuántos aumentos se encontraron durante esa secuencia. Por ejemplo, para $25 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 $33 a + 2$ ; para $22 a + 1$ solo hay 1 aumento a medida que 1 sube a 2 y baja 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á $2 \times 3 k a - 1$ . El factor de 3 que multiplica $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 de 4 aplicaciones de $f$ . Sin embargo, si esos números más pequeños continúan hasta 1, depende del valor de $a$ .

Como un sistema de etiquetas

Para la función Collatz en la forma

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

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

a \to bc

b \to a

c \to aaaa

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 inferior 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 práctico).

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 números enteros positivos. Dejando de lado el ciclo 0 → 0 que no se puede ingresar desde el exterior, hay un total de cuatro 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 conocido ciclo para positivo $n$ :

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	Longitud del ciclo del valor secundario	Longitud 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 - 55 → −164 → −82 → −41 → −122 → −61− → −182 → ,91 - 91 → −272 → −136 → −68 → −34 → −17 ...	7	18

La conjetura de Collatz generalizada es la afirmación de que todo número entero, iterado por $f$ , eventualmente cae en uno de los cuatro ciclos anteriores o el ciclo 0 → 0. (El ciclo 0 → 0 solo se incluye para completar).

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 'incluso' según que su numerador sea 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 'raro' dicho 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.

Al usar el "atajo" definición del mapa de Collatz, se sabe que cualquier secuencia de paridad periódica es generada por exactamente un racional. Por el contrario, se conjetura que todo racional con un denominador impar tiene una secuencia de paridad eventualmente cíclica (conjetura de periodicidad).

Si un ciclo de paridad tiene una longitud $n$ e incluye números impares exactamente $m$ veces en los índices $k 0 < \dots < k m -1$ , entonces el único racional que genera inmediata y periódicamente este ciclo de paridad es

{frac {3^{m-1}2^{k_{0}}+cdots +3^{0}2^{k_{m-1}}}{2^{n}-3^{m}}}.

()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

{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) es producido 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 se puede dividir 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 un múltiplo de 3, entonces todas las iteraciones tienen el mismo denominador y la secuencia de numeradores se puede obtener aplicando el " $3 n + d$ " generalización de la función de Collatz

{displaystyle T_{d}(x)={begin{cases}{frac {x}{2}}&{text{if }}xequiv 0{pmod {2}},\[4px]{frac {3x+d}{2}}&{text{if }}xequiv 1{pmod {2}}.end{cases}}}

Extensión 2-ádica

La función

{displaystyle T(x)={begin{cases}{frac {x}{2}}&{text{if }}xequiv 0{pmod {2}}\[4px]{frac {3x+1}{2}}&{text{if }}xequiv 1{pmod {2}}end{cases}}}

mathbb {Z} _{2}

Define el vector función $Q$ Actuando $mathbb {Z} _{2}$ como

{displaystyle Q(x)=sum _{k=0}^{infty }left(T^{k}(x)mod 2right)2^{k}.}

La función $Q$ es una isometría 2-adic. En consecuencia, cada secuencia de paridad infinita ocurre exactamente para un entero 2-adic, por lo que casi todas las trayectorias son acíclicas en $mathbb {Z} _{2}$ .

Una formulación equivalente de la conjetura de Collatz es que

{displaystyle Qleft(mathbb {Z} ^{+}right)subset {tfrac {1}{3}}mathbb {Z}.}

Iterar sobre números reales o complejos

Parcela de Cobweb de la órbita 10-5-8-4-2-1-2-1-2-1-etc. en la extensión real del mapa de Collatz (optimizado por reemplazar "

3 n + 1

con "

(3) n + 1)/2

El mapa de Collatz (con acceso directo) se puede ver como la restricción a los números enteros del mapa suave

{displaystyle f(z)={frac {1}{2}}zcos ^{2}left({frac {pi }{2}}zright)+{frac {3z+1}{2}}sin ^{2}left({frac {pi }{2}}zright).}

Collatz mapa fractal en un barrio de la línea real

Las iteraciones de este mapa en la línea real conducen a un sistema dinámico, más investigado por Chamberland. Demostró que la conjetura no se cumple para números reales positivos ya que hay infinitos puntos fijos, así como órbitas que se escapan monótonamente al infinito. La función $f$ tiene dos ciclos de atracción del período 2, $(1; 2)$ y $(1.1925...; 2.1386...)$ . Además, se supone 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). El límite entre la región coloreada y los componentes negros, es decir, el conjunto de Julia de $f$ , es un patrón fractal, a veces llamado & #34;Collatz fractal".

Optimizaciones

Compensación espacio-tiempo

La sección Como una secuencia de paridad anterior brinda una forma de acelerar la simulación de la secuencia. Para avanzar $k$ pasos en cada iteración (usando el $f$ de esa sección), divide el número actual en dos partes, $b$ (el $k$ bits menos significativos, interpretados como un número entero), y $a$ (el resto de bits como un número entero). El resultado de avanzar $k$ viene dado por

f k (22) 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 $k$ -números de bits $b$ , donde $d (b, k)$ es el resultado de aplicar el estilo $f$ función $k$ veces a $b$ , y $c (b, k)$ es el número de números impares encontrados en el camino. 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, 5) = { 0, 3, 2, 2, 2, 4, 1, 4, 1, 3, 2, 3, 4, 1, 2, 3, 3, 3, 1, 3, 3, 3, 3, 2, 3, 2, 4, 3, 4, 4, 5 },

d

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

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

Restricciones modulares

Con el propósito especial de buscar un contraejemplo a la conjetura de Collatz, este cálculo previo 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$ , la desigualdad

f k (22) k a + b) = 3 c () b) a + d () b) k a + b

es válido para todos los $a$ , entonces el primer contraejemplo, si existe, no puede ser $b$ módulo $2 k$ . 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, hay un estilo $k$ para los que se cumple tal 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 aumenta $k$ , la búsqueda solo necesita verificar esos residuos $b$ que no se eliminan con valores inferiores de $k$ . Solo sobrevive una fracción exponencialmente pequeña de los residuos. Por ejemplo, los únicos residuos sobrevivientes mod 32 son 7, 15, 27 y 31.

Función de Siracusa

Si $k$ es un entero impar, entonces $3 k + 1$ es par, entonces $3 k + 1 = 2 a k'$ con $k'$ impar y $a \geq 1. La función Syracuse es la función f del conjunto I de enteros impares dentro de sí mismo, para los cuales f (k) = k' (secuencia A075677 en la OEIS).$

Algunas propiedades de la función Syracuse son:

Para todos $k ▪ I$ , $f (4 k + 1) f () k)$ . Porque $3(4) k + 1) + 1 = 12 k + 4 = 4(3) k + 1)$ .)
En generalidad: Para todos $p \geq 1$ y extraño $h$ , $f p - 1 (22) p h -1) = 2 \times 3 p - 1 h - 1$ . (Aquí) $f p - 1$ es la notación de la iteración de funciones.)
Para siempre $h$ , $f (22) h - 1) \leq 3 h - 1 / 2$

La conjetura de Collatz es equivalente a la afirmación de que, para todos los $k$ en $I$ , existe un número entero $n \geq 1$ tal que <span class="texhtml" fⁿ(k) = 1.

Generalizaciones indecidibles

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

Específicamente, consideró funciones de la forma

{displaystyle {g(n)=a_{i}n+b_{i}};;,{text{where}};{nequiv i{pmod {P}}}}

a 0, b 0,... a P - 1, b P - 1

g () n)

La función Collatz estándar viene dada por $P = 2$ , $a 0 = 1 / 2$ , $b 0 = 0, a 1 = 3, b 1 = 1 . Conway demostró que el problema:$

Dado

g

n

, hace la secuencia de iterates

g k () n)

¿Lista 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

hace la secuencia de iterates

g k () n)

1, para todos

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 demostraron que el problema anterior es, de hecho, indecidible e incluso superior en la jerarquía aritmética, específicamente $Π 02$ -completo. Este resultado de dureza se mantiene incluso si se restringe la clase de funciones $g$ fijando el módulo $P$ a 6480.

En la cultura popular

En la película Incendies, un estudiante graduado en matemáticas puras explica la conjetura de Collatz a un grupo de estudiantes universitarios. Suspende sus estudios por un tiempo para abordar algunas preguntas no resueltas sobre el pasado de su familia. Al final de la película, la conjetura de Collatz presagia un descubrimiento inquietante y difícil que hace sobre su familia.

Contenido relacionado

Más resultados...