¿La conjetura de Collatz sigue en pie si reemplazo el 3 con otras probabilidades positivas?

Answer 1

La variación “[matemática] n + 1 [/ matemática]” es muy fácil. La conjetura es cierta en este caso, y usted puede demostrarlo fácilmente. Por supuesto, esta es la razón por la cual la conjetura original de Collatz tiene esa [matemática] [/ matemáticas] allí.

Para otros multiplicadores, puede encontrar rápidamente que no todos los números convergen a [matemáticas] 1 [/ matemáticas], y que hay otros ciclos pequeños. Por ejemplo, con [matemáticas] 5n + 1 [/ matemáticas] encontrará

[matemáticas] 13 \ a 66 \ a 33 \ a 166 \ a 83 \ a 416 \ a 208 \ a 104 \ a 52 \ a 26 \ a 13 [/ matemáticas]

De hecho, esperaría que existan caminos infinitos para [matemáticas] 5n + 1 [/ matemáticas] (y superiores), ya que la tasa de crecimiento promedio es positiva. Sin embargo, no estoy seguro de si esto se sabe.

En términos generales, todos estos problemas son difíciles (a menos que sean obvios, como con [matemáticas] n + 1 [/ matemáticas]). Se sabe que una generalización natural de la conjetura de Collatz es indecidible.

Answer 2

Tratemos de llegar a una conjetura y su contraejemplo simultáneamente. El contraejemplo que buscaremos es un ciclo que no incluye 1.

Suponga que [matemática] 2x + 1 [/ matemática] es un número impar. Lo multiplicamos por [matemáticas] k [/ matemáticas] y sumamos 1. Eso nos da un número par. Si ese número par es una potencia de 2 mayor que [matemática] x [/ matemática], entonces la regla K-Collatz dará como resultado un ciclo.

[matemáticas] k (2x + 1) +1 = 2 ^ j (2x + 1) [/ matemáticas]

[matemáticas] 2kx + k + 1 = 2 ^ {j + 1} x + 2 ^ j [/ matemáticas]

[matemáticas] (2k-2 ^ {j + 1}) x = 2 ^ j – k – 1 [/ matemáticas]

Si trazamos esto para j fijo, es una parábola con solo dos soluciones enteras (x = 0 yx = -1, por lo que no es particularmente útil).

¿Qué tal un ciclo más largo? Intentemos [matemática] 2x + 1 \ rightarrow k (2x + 1) +1 \ rightarrow kx + 1 \ rightarrow k (kx + 1) +1 = 2 ^ j (2x + 1) [/ math] en su lugar. Tenga en cuenta que [math] x [/ math] tiene que ser par para que esto sea un ciclo.

[matemáticas] k ^ 2x + k + 1 = 2 ^ {j + 1} x + 2 ^ j [/ matemáticas]

[matemáticas] (k ^ 2–2 ^ {j + 1}) x = 2 ^ j – k – 1 [/ matemáticas]

[matemáticas] \ displaystyle x = \ frac {2 ^ jk-1} {k ^ 2 – 2 ^ {j + 1}} [/ matemáticas]

Esto también carece de soluciones enteras inmediatamente útiles, aunque obviamente es posible x = 0. Suponga que un primo [matemático] p [/ matemático] divide tanto arriba como abajo. Entonces

[matemáticas] p \ mid (k – 2 ^ j) (k + 2 ^ j) [/ matemáticas]

Entonces, si [matemática] p \ mid k – 2 ^ j = (-1) (2 ^ jk) [/ matemática], entonces [matemática] p \ not \ mid (2 ^ j – k) – 1 [/ matemática ] Eso es malo si queremos terminar con un número entero, por lo que debe ser que [math] k – 2 ^ j = \ pm 1 [/ math].

Si [matemáticas] k = 2 ^ j + 1 [/ matemáticas], entonces [matemáticas] x = \ frac {2 ^ j – (2 ^ j + 1) -1} {(2 ^ j + 1) ^ 2 – 2 ^ {j + 1}} = \ frac {-2} {2 ^ {2j} + 2 ^ {j + 1} + 1 – 2 ^ {j + 1}} = \ frac {-2} {2 ^ {2j} +1} [/ math] que no es positivo ni entero, excepto [math] j = 0 [/ math] [math], x = -1 [/ math].

Si [matemática] k = 2 ^ j -1 [/ matemática], entonces [matemática] x = 0 [/ matemática].

Entonces, si bien esto podría haber sido interesante para mí, todo lo que logré mostrar es que K-Collatz carece de estos dos ciclos simples, sin importar cuál sea K. Y veo que Alon ya dio un ejemplo concreto de un ciclo para K = 5.

Answer 3

Hay dos partes: [matemáticas] mn [/ matemáticas] y [matemáticas] + x [/ matemáticas]. [Math] mn [/ math] impulsa el crecimiento de la función, y crece rápidamente si aumenta [math] m [/ math] aunque sea un poco. Por ejemplo, con [matemática] m = 5 [/ matemática], [matemática] 111 [/ matemática] crece a [matemática] 110688400113 [/ matemática] en la iteración 300. [Math] + x [/ math] es el comodín porque desmorona todos los factores primos, ya que convierte el entero de impar a par. [math] 1 [/ math] es el comodín más poderoso porque no produce ningún sesgo en los factores primos resultantes. Es este sesgo el que produce el ciclismo para otras [matemáticas] x [/ matemáticas] impares.

Puede probar la ciclicidad muy fácilmente utilizando cualquier otra [matemática] x [/ matemática] impar. Todos los demás [matemática] 3n + x [/ matemática] s ([matemática] 3, 5, 7, [/ matemática] etc.) de ciclo rápido cuando [matemática] n [/ matemática] es un múltiplo de [matemática] x [/ matemáticas]. Por ejemplo, tome un bucle corto como este cuando [matemática] m = 3 [/ matemática] y [matemática] x = 9 [/ matemática] (y la entrada es [matemática] 72 [/ matemática], comenzando en la 23ª iteración ): [matemáticas] 18 (3,3,2), 9 (3,3), 36 (3,3,2,2), 18 (3,3,2) [/ matemáticas]

La singularidad de [math] 3n + 1 [/ math] es que 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.

Answer 4

Realmente no. Si reemplaza 3 por 1, se convierte en n + 1. En ese caso, sí, cualquier número eventualmente llegará a 1. Sin embargo, si se reemplaza por 5, se convierte en 5n + 1. En este caso, no todos los números llegan a 1. Solo unos pocos números lo hacen. Números como 3,51,819,13107,209715, etc. son números que regresan a 1. Lo he comprobado solo hasta 5n +1. No estoy seguro acerca de otros números impares. Puedes revisarlos, ¡házmelo saber!

Answer 5

No se ha probado mucho. La heurística ingenua aquí es que para el Collatz original un número es igual de probable que sea par o impar, si es multiplicado por [matemática] 1/2 [/ matemática], y si es impar multiplicado por [matemática] 3/2 [ /matemáticas]. Como [matemática] (3/2) (1/2) <1 [/ matemática] se tiene la expectativa de que las secuencias tenderán a disminuir. Debido a que no hay ciclos entre números pequeños además de [matemática] 4,2,1 [/ matemática] la conjetura parece plausible.

Para [matemáticas] 5n + 1 [/ matemáticas] esta heurística ya no parece válida. En cambio, porque [matemáticas] 5/4> 1 [/ matemáticas] uno puede esperar plausiblemente que muchas de las secuencias lleguen al infinito, y la experimentación numérica parece confirmar esto como Alon Amit ya mencionó.

Answer 6

Se sabe que el problema de tipo collatz tiene algunos bucles. También la conjetura de Matthews está sin resolver. Problema Collatz – de Wolfram MathWorld