43 votos

Collatz relajada 3x +1 conjetura

El Collatz $3x+1$ conjetura afirma que cualquier entero positivo, eventualmente, puede ser reducido a $1$ por iterativo de la aplicación de los mapas de $x \mapsto 3x+1$ siempre $x$ es impar y $x \mapsto x/2$ siempre $x$ es incluso.

Mientras que la conjetura de Collatz todavía está abierta, me pregunto si el siguiente relajado versión es más simple. En este relajado versión nos permite aplicar los mapas en cualquier orden para mantener a los números enteros. Es decir, si $x$ es impar, todavía tenemos que aplicar el $x \mapsto 3x+1$ mapa; pero incluso para $x$, tenemos la libertad de elegir entre el $x \mapsto 3x+1$ e $x \mapsto x/2$. La conjetura es que para cualquier entero positivo, se puede reducir a $1$ con algunos secuencia iterativa de los mapas.

Claramente, la conjetura de Collatz implicaría el relajado versión. Pero puede suceder que el relajado versión es mucho más simple. Es?

La pregunta es inspirado por la discusión de la secuencia http://oeis.org/A109732 que es una permutación de los enteros positivos impares iff relajado versión de la $3x-1$ variante de la conjetura de Collatz sostiene.

La ACTUALIZACIÓN. El número mínimo de iteraciones para llegar a $1$ en este relajado versión está dada por http://oeis.org/A127885 y este número es a menudo menor que el de la conjetura de Collatz dada por http://oeis.org/A006577 .

6voto

Curt Puntos 302

Voy a escribir $\longrightarrow$ algunos estándar iteraciones y $\implies$ para algunos posiblemente no estándar de iteraciones. El relajado conjetura de Collatz es que para todos los $x$, $x \implies 1$. Voy a llamar a contraejemplos a la conjetura de escapados.

Primero de todos, ya que es un buen ejemplo de la notación, un lexema: para todos los $a$, $4 a \implies 9 a + 1$.

Prueba: $4a \implies 12 a + 1 \longrightarrow 36a + 4 \longrightarrow 18a + 2 \longrightarrow 9 a + 1$.

$\square$

Ahora aquí es lo que voy a intentar mostrar:

Teorema: Si $x$ es el más pequeño fugitivo, a continuación,$4x \implies 1$.

Prueba: Por consideraciones elementales, $x \equiv 3 \pmod{4}$. Si $x \equiv 2 \pmod{3}$,, a continuación,$\frac{2 x - 1}{3} \longrightarrow 2 x \longrightarrow x$. Así que en este caso, $2 x$ no puede ser un fugitivo, y tampoco se puede de $4 x$.

El siguiente caso es $x \equiv 0 \pmod{3}$. Escribir $x = 12k+3$. Usando el lema, $4x \implies 27k+7$. Observar que $x > 9k+2 \rightarrow 27k+7$ si $k$ es impar. Ahora si $x \equiv 15 \pmod{24}$, también tenemos que $4x \implies 1$.

También es posible que $x \equiv 3 \pmod{24}$. En ese caso, tenemos $x = 24 j + 3$ e $x \longrightarrow 27j+4$. Esto significa $j$ no se puede aún. Así que perforar hacia abajo de nuevo, con $x = 48i + 27 \longrightarrow 81i+49$. Esto significa $i$ no puede ser impar. Pero también, $4x = 4(48i+27) \implies 81i + 92$, por lo que si $i$ es incluso, el siguiente paso nos lleva en $x$. Esto cubre todos los $x \equiv 0 \pmod{3}$ de los casos.

Hasta ahora, nuestro resultado es que si $x \implies 4x$,, a continuación,$x \equiv 7 \pmod{12}$. Ahora voy a manejar en ese caso. Supongamos $x \implies 4x$ e $x = 24k + 7$. Entonces tenemos:

$4x = 4(24k+7) \implies 9(24k+7)+1 = 216k+64 \longrightarrow 108k+32 \longrightarrow 54k+16$.

Pero también, $18k+5 \longrightarrow 54k+16$. Esto significa $18k+5$ es un fugitivo, pero no puede ser, ya que es menos de $x$. Por lo que la hipótesis es falsa y tenemos $x = 24k + 19$ lugar.

Ahora, considere la posibilidad de:

$4x = 4(24k+19) \implies 216k + 172 \longrightarrow 108k + 86 \longrightarrow 54k + 43 \longrightarrow 162k + 130 \longrightarrow 81k+65$.

Por un razonamiento similar, $k \neq 3 \pmod{4}$, o de lo contrario nos puede continuar la cadena dos pasos más para obtener un fugitivo menos de $x$. Finalmente,

$x = 24k+19 \longrightarrow 72k+58 \longrightarrow 36k + 29 \longrightarrow 108k + 88 \longrightarrow 54k + 44 \longrightarrow 27k + 22$.

muestra que $k$ no puede ser, incluso, y la sustitución de $k = 4 j + 1$:

$27k + 22 = 108j + 49 \longrightarrow 324j + 148 \longrightarrow 162j + 74 \longrightarrow 81j + 37 < x$

completa la prueba, ya que todos los casos.

$\square$

Corolario: si la conjetura de Collatz es falsa y la más pequeña contraejemplo lleva de nuevo a sí mismo, entonces ese número no es un contraejemplo a la relajada conjetura de Collatz. En otras palabras, si $y$ es el menor número de satisfacciones $\neg(y \longrightarrow 1)$,, a continuación, $y \longrightarrow y$ implica $y \implies 1$. Esta es una versión más débil de lo que originalmente pensé que había probado.

Corolario: Si $4x$ es un fugitivo, entonces no es un fugitivo menor que $x$. Esto me sugiere un descenso recursivo estrategia en la que intento mostrar $z \implies 4k < 4x$. Pero no está claro si compuadora se nos lleva a ninguna parte más.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X