¿Es solucionable la conjetura de Collatz?

Answer 1

Cuando supe por primera vez sobre la Conjetura de Collatz, me resistí fuertemente porque no me pareció un tema válido para la teoría de números, como se dijo . Como se dijo, puede parecer un rompecabezas lógico de tipo bastante banal. Ahora modifico esa opinión en función de la dificultad de descartar la posibilidad de un ciclo. Así es como creo que la conjetura estaría mejor expresada:

¿La multiplicación de una [matemática] n [/ matemática] por [matemática] 3 [/ matemática] , la suma por [matemática] 1 [/ matemática] y la división por [matemática] 2 [/ matemática] hasta que el número sea impar ¿Alguna vez has dado el mismo número dos veces ?

Probar que una secuencia de enteros nunca se repite es la teoría de los números equivalente a demostrar que un número real es irracional (como es el caso de la raíz cuadrada de todos los números naturales no cuadrados). Es fundamental, pero aparentemente no se ha encontrado una técnica tan general. Todavía creo que el problema es solucionable, y puede que no sea tan difícil como se supone.

Anexo 1: Paul Erdős fue un gran matemático, pero no era tan inteligente en lo que respecta a la lógica del día a día. Él no comprendió de inmediato el cambio de probabilidad en el problema de Monty Hall hasta que se lo explicaron. Ahora lo menciono porque dijo de la Conjetura de Collatz: “Las matemáticas pueden no estar listas para tales problemas”. También lo menciono porque, por cierto, estudió una propiedad numérica (teorema de Erdős-Kac) que podría ayudar a resolver esta conjetura.

Anexo 2: Sin duda sus palabras le dieron mucha credibilidad a la conjetura. Pero ve con tu instinto. ¿Esta rutina de “multiplicar por 3, sumar 1, dividir por 2” no te recuerda algo trivial? Sí, esos juegos numéricos de lectura mental que a los niños les gusta torturar a sus padres y hermanos que siempre producen el mismo número. Sí, podríamos estar descendiendo al nivel de trucos de salón aquí, y del tipo en que cualquier niño inteligente podría encontrar la solución.

Hay tres problemas a resolver en la Conjetura de Collatz. Los dos primeros no son realmente problemas en absoluto. El tercer problema es real, y lo guardaré hasta el final de mi respuesta y sugeriré la solución más simple.

“Problema 1”: (Deje a un lado las [matemáticas] 3 [/ matemáticas] por un momento; verá por qué no importa en el problema 2.) ¿Qué tipo de número impar [matemáticas] +1 [/ matemáticas] produce un número par que es divisible más de una vez por [matemáticas] 2 [/ matemáticas]? Si el par [math] n [/ math] es divisible solo una vez, entonces la secuencia continuará creciendo cada vez que se multiplique por [math] 3 [/ math]: dos pasos hacia atrás, tres pasos hacia adelante .

Solución: La mitad de los números pares son divisibles por [matemáticas] 2 [/ matemáticas] dos veces o más … es decir, tienen factores [matemáticas] 2 * 2 … [/ matemáticas]. Esto es aparte del conjunto de números pares para los cuales [matemática] 2 [/ matemática] es el número primo único o distinto: por ejemplo, [matemática] 1024 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 [/ matemáticas]. Este tipo de números “poderes de [matemáticas] 2 [/ matemáticas]” se denotan [matemáticas] ω (n) = 1 [/ matemáticas] por Erdős – Kac. (La [matemática] 1 [/ matemática] es para un factor primo, que para un número par debe ser [matemática] 2 [/ matemática].) Si la secuencia de Collatz golpea a uno de estos números, se acabó el juego.

“Problema 2”: hay un conjunto infinito de números pares de la forma [matemáticas] 3n + 1 [/ matemáticas]. De hecho, cada sexto número es de esta forma, por supuesto. ¿Los teóricos de los números que miran el Monte Everest de este problema buscan un [matemático] 3n + 1 [/ matemático] que nunca puede dividirse en un número par [matemático] ω (n) = 1 [/ matemático]?

Solución: Una regla de aritmética gobierna la recurrencia de [matemáticas] 3n + 1 [/ matemáticas] e incluso números de tipo [matemáticas] ω (n) = 1 [/ matemáticas]. Si tales intersecciones existen, lo que hacen infinitamente, por aritmética, entonces cada secuencia debe terminar siempre que el problema 3 sea solucionable . Mirando algunos productos de [matemáticas] 3n + 1 [/ matemáticas]:

3 * 5 + 1 = 16
3 * 7 + 1 = 22
3 * 9 + 1 = 28
3 * 11 + 1 = 34
3 * 13 + 1 = 40
3 * 15 + 1 = 46
3 * 17 + 1 = 52
3 * 19 + 1 = 58
3 * 21 + 1 = 64

Vemos que [math] 16 [/ math] y [math] 64 [/ math] son ​​ambos [math] ω (n) = 1 [/ math] números. De hecho, cada segundo poder de [matemática] 2 [/ matemática] tiene la forma [matemática] 3n + 1 [/ matemática]: [matemática] 16, 64, 256, 1024… [/ matemática]. Como sistema probabilístico que funciona bajo estas reglas, el punto final sigue siendo determinista.

¡Maricón! La conjetura de Collatz se ha desmaterializado. No tiene sustancia ni valor. ¡Buen viaje! En realidad no, en todos los aspectos. Eso fue sólo una exuberante ilusión. Tiene partes móviles más interesantes que esto.

Por cierto
Tengo la mejor analogía: un juego de “Serpientes ( también conocido como Chutes) y Escaleras” en el que siempre pierdes.

---

Una fuerza entrópica que actúa en un sistema es una fuerza resultante de la tendencia termodinámica de todo el sistema a aumentar su entropía, en lugar de una fuerza microscópica subyacente particular. (Cito un artículo de Wikipedia aquí). Esto sugiere por qué este no es un buen tema para la teoría de números, donde generalmente se estudian los sistemas estáticos en lugar de los dinámicos. Este sistema parece ser aleatorio, pero dentro de ciertos parámetros que solo pueden tener un resultado. ¿Por qué?

Rocas, tijeras, papel

Según las reglas del juego, hay más oportunidades para dividir un número que multiplicarlo. Claro, la multiplicación por [matemática] 3 [/ matemática] excede la división por [matemática] 2 [/ matemática], y entonces usted ve aumentos repentinos en las secuencias numéricas. Pero la división por [matemática] 2 [/ matemática] puede ocurrir varias veces, tantas veces como haya factores de [matemática] 2 [/ matemática].

Por ejemplo, [matemática] 304 [/ matemática] es divisible cuatro veces porque sus factores son [matemática] 2 * 2 * 2 * 2 * 19 [/ matemática]. Entonces, el “ascenso” es de [matemáticas] 101 [/ matemáticas] y el “descenso” es de [matemáticas] 19 [/ matemáticas]. En general, hay muchos más descensos (divisiones entre [matemáticas] 2 [/ matemáticas]) que ascensos (multiplicaciones por [matemáticas] 3 [/ matemáticas]). Incluso sin una potencia de [matemática] 2 [/ matemática], el descenso sigue siendo un acelerador porque aproximadamente la mitad de todas las secuencias golpean la terminal [matemática] 5 [/ matemática] [matemática] (3 * 5 + 1 = 16 [/ matemática ]).

Esta es la clave: este es el hecho entrópico: la división por [matemática] 2 [/ matemática] ocurrirá varias veces secuencialmente porque cada segundo número par tiene dos o más factores primos que son [matemática] 2 [/ matemática]: que es, [matemáticas] 2 * 2 … [/ matemáticas]).

Secuencia para 2467 : 134 iteraciones

El juego está arreglado

Ningún número divisible por [matemática] 3 [/ matemática] puede estar en cualquier secuencia, excepto como el primer número.

Cada [matemática] n [/ matemática] en [matemática] 3n + 1 [/ matemática] para una potencia de [matemática] 2 [/ matemática] tiene un último dígito [matemática] 1 [/ matemática] o [matemática] 5 [ /matemáticas].

16 = 5
64 = 2 1
255 = 8 5
1024 = 34 1
4095 = 136 5
16384 = 546 1

(Cabe señalar que aunque [matemáticas] 64 [/ matemáticas] es obviamente una potencia de [matemáticas] 2 [/ matemáticas], nunca puede comenzar una secuencia de descenso porque [matemáticas] 21 [/ matemáticas] es un múltiplo de [matemáticas] 3 [/ matemáticas]. Esta advertencia probablemente se aplica a otros poderes de [matemáticas] 2 [/ matemáticas].)

Cada último dígito de los números en una secuencia debe cambiar con cada operación exactamente de esta manera:

1 -> 4 -> 2 o 7
3 -> 0 -> 0 o 5
5 -> 6 -> 3 u 8
7 -> 2 -> 1 o 6
9 -> 8 -> 4 o 9

Problema 3: esto lleva a la mosca en la pomada. Esa es la posibilidad de ciclicidad, de una secuencia que cae en un ciclo repetitivo. A primera vista, esto parece un evento de alta probabilidad ya que solo un número tiene que repetirse para que esto suceda. Sin embargo, sugiero que la razón por la que nunca se ha observado que esto ocurra no es un misterio.

Ciclo de ruptura

Lo que hace que [math] 3n + 1 [/ math] sea distinto de cualquier otro [math] 3n + x [/ math] es que no es cíclico. Todos los demás valores de [matemática] x [/ matemática] se vuelven cíclicos cuando forman una unidad de multiplicación de igualdad [matemática] x * 2 * 2 = 3n + x [/ matemática] si [matemática] n = x [/ matemática]. Por ejemplo, 3 * 7 + 7: 28 (7,2,2), 14 (7,2), 7 (7), 28 (7,2,2).

Esto no puede suceder con [matemáticas] 1 [/ matemáticas]: no es un factor primo. No produce ningún sesgo en los factores primos resultantes.

Ahora [math] 3n + 1 [/ math] tiene otra propiedad que destruye el ciclo: nunca puede ser un múltiplo de [math] 3 [/ math] porque nunca puede tener [math] 3 [/ math] como factor . Cada sexto entero par tiene [matemática] 2 * 3 [/ matemática] como factores, y cada sexto entero impar tiene [matemática] x * 3 [/ matemática] como factores. Todos esos compuestos, un tercio de ellos, están ausentes de las secuencias de Collatz. Ese es solo el elefante en la habitación que no puedes ignorar.

Para que la no ciclicidad de [matemática] 3n + 1 [/ matemática] sea homogénea, la operación de [matemática] n → * 3 → +1 → / 2 [/ matemática] … no debe ser idempotente. No puede volver al mismo valor bajo ninguna circunstancia. Imagine una escalera de caracol ascendente y una escalera de caracol descendente. Son diferentes escaleras. El conjunto de productos y el conjunto de cocientes son disjuntos.

---

Qué diferencia hace un par de meses en la evolución de las ideas:

Parte 1: Collatz y Congruencia

Parte 2: ¿Cómo funciona un ciclo de secuencia?

Parte 3: La insignificancia de la uniformidad

Parte 4: exponentes de 2 y tiempo de detención finito

Answer 2

“Los grandes pensadores siempre se han encontrado con la oposición de mentes mediocres”. – Albert Einstein . [1]

¡¡Si!! ¡La conjetura de Collatz es bastante interesante y solucionable! Este es el por qué:

Considere la siguiente prueba de la conjetura de Collatz:

La probabilidad (la secuencia de Collatz no converge a una) es

∴ La probabilidad (la secuencia de Collatz no converge a una) es cero.

Notas:

Concluimos que la conjetura de Collatz es cierta.

Una nota importante:

El valor, l_m = 1, que implica división por dos en el proceso de Collatz, ocurrirá con la misma frecuencia que todos los demás valores, l_m> 1, lo que implica división por cuatro o por ocho o por dieciséis o por treinta y dos, … en el Proceso de Collatz de acuerdo con nuestros cálculos de probabilidad y de acuerdo con la Ley de Números Grandes. Por lo tanto, esperamos que la división por dos ocurra el 50% de todas las divisiones posibles en el procesamiento de Collatz. Ese hecho explica cualquier crecimiento en la secuencia de Collatz, y también explica por qué la secuencia de Collatz siempre convergerá a una.

Un enlace de prueba de conjetura de Collatz:

Prueba de conjetura de Collatz .

Enlaces de referencia: El problema 3x + 1: una visión general ;

Un estudio de caso de la conjetura de Collatz .

*****

Función de software Mathematica 11, f [], para simulación de datos:

f [m_]: = (

n = m;

Imprimir [n];

prob = 1 .;

Mientras [n> 1, n = 3 * n + 1;

x = n; i = 0; cnt = 0; icnt = 0;

Mientras[

EvenQ [x], ++ i;

x = x / 2];

s = 1 – 2 ^ (- i);

cnt = cnt + 1;

Si [i == 1, icnt = icnt + 1];

Imprimir [x];

prob = prob * s;

n = x;

];

Devuelve [{m, prob, cnt, icnt, 100. * icnt / cnt}]

);

Ejemplo 1:

f [n_0 = 1367] produjo una probabilidad (prob) igual a 0.0245548 antes de la secuencia de Collatz de enteros impares,

{1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1},

convergido a uno;

Ejemplo 2

{ n_0 = 1917424378915227003508542412844973284190406292736261788098013,

problema = 2.14803 * 10 ^ -104,

cnt = número de enteros impares generados de la secuencia de Collatz = 541,

icnt = número de veces que l_m o i es igual a uno = 269,

icnt / cnt = 49.7227%};

Ejemplo 3

{n_0 = 1134322358892035783221922112828664036984286481192427929865901,

prob = 1.30642 * 10 ^ -113,

cnt = número de enteros impares generados de la secuencia de Collatz = 573,

icnt = número de veces que l_m o i es igual a uno = 301,

icnt / cnt = 52.5305%};

Ejemplo 4

{nx0021346294170249129484267610567431365440581190958189557170758121139151539071578979902206895286197857360174461437777776779779776779

problema = 5.118883814495941 * 10 ^ -344,

cnt = número de enteros impares generados de la secuencia de Collatz = 1772,

icnt = número de veces que l_m o i es igual a uno = 902,

icnt / cnt = 50.9029%};

Ejemplo 5:

{ n_0 =,

problema = 8.737445781552508 * 10 ^ -906,

cnt = número de enteros impares generados de la secuencia de Collatz = 4745,

icnt = número de veces que l_m o i es igual a uno = 2361,

icnt / cnt = 49.7576%};

Ejemplo 6

{,

Prob = 7.060409409804900 * 10 ^ -3120,

cnt = número de enteros impares generados de la secuencia de Collatz = 16257,

icnt = número de veces que l_m o i es igual a uno = 8155,

icnt / cnt = 50.163%} .

Esperábamos que icnt / cnt fuera del 50% de acuerdo con la Ley de números grandes cuando l_m = 1.

Los seis ejemplos son afirmaciones empíricas típicas de la teoría que prueba la conjetura de Collatz.

PD No hay excepciones (contraejemplos o ciclos) que refuten la Conjetura de Collatz. Y desafío a cualquiera a encontrar uno. De lo contrario, es un acto de pura ficción sugerir tales cosas sin pruebas.

Notas al pie

[1] La respuesta de David Cole a ¿Los expertos siempre tienen la razón?

Answer 3

A2A: No sabemos si la Conjetura de Collatz es válida o no. Es por eso que se llama una “conjetura”.

Tenga en cuenta que una conjetura no es algo que resuelva. Es algo que puede esperar resolver. La resolución puede tomar la forma de una prueba de que la conjetura es verdadera o una prueba de que es falsa. Hasta ahora, ninguna prueba, de ninguna manera, se ha ofrecido para la Conjetura de Collatz. Para obtener más información sobre el tema, consulte la conjetura de Collatz – Wikipedia.

Actualización: David Cole sigue editando los detalles de su pregunta, aparentemente tratando de defender su uso de “resuelto” en la pregunta en oposición a mi afirmación de que es un uso inapropiado. Una conjetura es una declaración, no un problema. Sin embargo, resolver una conjetura es un problema legítimo. La pregunta que debería hacerse es si la conjetura es resoluble o no. La ironía es que dice saber la respuesta, entonces, ¿por qué hace la pregunta? De hecho, afirma haberlo resuelto afirmativamente. Su afirmación de haber logrado eso es extremadamente dudosa.

Answer 4

El hecho de que todavía no se haya encontrado un contraejemplo parece reflejar que hay algo en la verdad de la conjetura. Mi primera intuición sería probar un argumento por inducción, pero este enfoque es tan fácil que estoy seguro de que se ha intentado antes.

En respuesta a su pregunta: no sé si la conjetura se puede probar o no. Sin embargo, como la mayoría de las cosas que no puedo probar, trato de desarrollar la intuición utilizando modelos informáticos simples. Este sería fácil de configurar en 10 líneas. Esto no dará una prueba rigurosa, pero podrá convencerse de la validez de la declaración.