Autor Tema: Intento de demostración de Conjetura de Collatz

0 Usuarios y 1 Visitante están viendo este tema.

23 Junio, 2020, 12:01 am
Respuesta #20

Granmurillo

  • Junior
  • Mensajes: 37
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino

En general es fácil de probar por inducción que \( f(3^a2^b-1)=3^{a+1}2^{b-1}-1 \) y de ahí que \( f^{(n)}(2^n-1)=3^n-1 \).

Saludos.

Entonces veía \( f^n \) como el total de iteraciones mientras a lo que se referían con \( f^n \) era la cantidad de iteraciones que multiplicaban por \( 2^n \) un número impar \( 2^n-1 \). Entiendo.

¿Pero entonces existe una forma inductiva para demostrar la diferencia entre la cantidad de iteraciones \( f^n \) hasta 1 entre una \( n \) impar y su \( n+1 \) de un número \( 2^n+1 \) que da como resultado siempre una iteración adicional como indiqué en el ejemplo anterior?

23 Junio, 2020, 09:00 am
Respuesta #21

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,006
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Entonces veía \( f^n \) como el total de iteraciones mientras a lo que se referían con \( f^n \) era la cantidad de iteraciones que multiplicaban por \( 2^n \) un número impar \( 2^n-1 \). Entiendo.

No \( f^n=\underbrace{f\circ f\circ f\circ \ldots \circ f}_{n\textsf{ veces}} \) es aplicar la función de Collatz, \( n \) veces a un número. Es decir esta función:

\( f(x) = \begin{cases} x/2 \text{ si $x$ par} \\ {(3x+1)/2}\text{ si $x$ impar} \end{cases} \)

Citar
¿Pero entonces existe una forma inductiva para demostrar la diferencia entre la cantidad de iteraciones \( f^n \) hasta 1 entre una \( n \) impar y su \( n+1 \) de un número \( 2^n+1 \) que da como resultado siempre una iteración adicional como indiqué en el ejemplo anterior?

Si tomas \( N=2^{2k}-1 \), después de \( 2k \) iteraciones se llega a \( 3^{2k}-1 \). Esté número es siempre divisible por \( 4 \), por tanto con dos iteraciones más se llega a \( \dfrac{3^{2k}-1}{4} \).

Es decir desde  \( N=2^{2k}-1 \) en \( 2k+2 \) iteraciones se llega a \( \dfrac{3^{2k}-1}{4} \).

Si tomas \( N=2^{2k-1}-1 \), después de \( 2k-1 \) iteraciones se llega a \( 3^{2k-1}-1 \). Esté número es siempre divisible por \( 2 \), pero no por cuatro: por tanto con dos iteraciones más se llega a:

 \( \dfrac{3\cdot \dfrac{3^{2k}-1}{2}+1}{2}=\dfrac{3^{2k}-1}{4} \).

Es decir desde  \( N=2^{2k-1}-1 \) en \( 2k+1 \) iteraciones se llega a \( \dfrac{3^{2k}-1}{4} \).

Resumiendo si \( n \) es se llega desde \( 2^{n}-1 \) al mismo número que desde \( 2^{n-1}-1 \) pero con una iteración más; de ahí que para llegar \( 1 \) también se haga en exactamente una iteración más.

Saludos.

23 Junio, 2020, 03:55 pm
Respuesta #22

Granmurillo

  • Junior
  • Mensajes: 37
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino

Resumiendo si \( n \) es se llega desde \( 2^{n}-1 \) al mismo número que desde \( 2^{n-1}-1 \) pero con una iteración más; de ahí que para llegar \( 1 \) también se haga en exactamente una iteración más.


Pero eso solo pasa entre \( n \) y \( n+1 \) cuando \( n \) es impar. Cuando \( n \) es par en \( n+1 \) el total de las iteraciones es variable, puede ser menor o mayor.

Saludos.

23 Junio, 2020, 04:28 pm
Respuesta #23

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,006
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Pero eso solo pasa entre \( n \) y \( n+1 \) cuando \( n \) es impar. Cuando \( n \) es par en \( n+1 \) el total de las iteraciones es variable, puede ser menor o mayor.

Si, bien. Nadie dice lo contrario. Precisamente la demostración anterior está hecha para \( n=2k \), es decir, para \( n \) par.

Saludos.

23 Junio, 2020, 05:04 pm
Respuesta #24

Granmurillo

  • Junior
  • Mensajes: 37
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino

Si, bien. Nadie dice lo contrario. Precisamente la demostración anterior está hecha para \( n=2k \), es decir, para \( n \) par.


Y para el resto de números impares que se encuentran entre \( 2^n-1 \) y \( 2^{n+1}-1 \) habría que encontrar cuál es el patrón?

23 Junio, 2020, 05:06 pm
Respuesta #25

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,006
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Y para el resto de números impares que se encuentran entre \( 2^n-1 \) y \( 2^{n+1}-1 \) habría que encontrar cuál es el patrón?

¿Habría que encontrar para qué?. Fíjate que yo no me puesto a pensar mucho en nada de esto. Simplemente tu has observado una propiedad y yo te he indicado como probarla rigurosamente. No me estoy planteando nada más allá de eso.

Saludos.

23 Junio, 2020, 05:31 pm
Respuesta #26

Granmurillo

  • Junior
  • Mensajes: 37
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino

¿Habría que encontrar para qué?. Fíjate que yo no me puesto a pensar mucho en nada de esto. Simplemente tu has observado una propiedad y yo te he indicado como probarla rigurosamente. No me estoy planteando nada más allá de eso.


Pensaba que si el resto de números impares tuvieran patrones donde la diferencia total de las iteraciones fueran 1, 2, 3 o hasta 4 que son la cantidad de iteraciones entre el menor impar más bajo que calcula iteraciones directas dividiendo para 2 que es el 5 hasta el 1 y tuvieran una explicación como la has dado para \( 2^n-1 \) donde cada número impar tuviera una solución en otro número impar menor entonces podría ser una demostración completa de la conjetura... Sólo pensaba, era una opinión.

Saludos

13 Agosto, 2020, 07:11 pm
Respuesta #27

Granmurillo

  • Junior
  • Mensajes: 37
  • País: ec
  • Karma: +0/-0
  • Sexo: Masculino

P.D. De hecho para cualquier \( n \) natural uno siempre puede encontrar un número \( N \) tal que iterando \( n \) veces la función \(  f^{n)}(N)>N \). Basta tomar \( N=2^n-1 \).

Si tienes razón en que basta con tomar un número natural \( n \) de ese tipo, pero parece que es una propiedad exclusiva de todo número \( 4k+3 \) puesto que:

\( \frac{3(4k+3)+1}{2} = 2n+1 \)

\( \frac{12k+10}{2} = 2n+1 \)

\( 6k+5 = 2n+1 \)

\( 3(2k)+2(2)+1 = 2n+1 \)

es decir que luego de 2 iteraciones calcula otro número impar mayor que \( 4k+3 \) mientras que:

\( \frac{3(4k+1)+1}{2} = 2n+1 \)

\( \frac{12k+4}{2} = 2n+1 \)

\( 6k+2 = 2n+1 \)

\( 3(2k)+2 = 2n+1 \)

que es absurdo y por eso requeriría más de 2 iteraciones para calcular otro número impar que sería menor a \( 4k+1 \).

Luego de cierta cantidad de iteraciones hay 3 patrones además del revisado \( 2^k -1 \). Por lo observado \( 2^k -1 \) con \( k \) impar calcula los mismos valores que \( 2^{k+1} -1 \), es decir que para alcanzar los valores de \( 2^{k+2} -1 \) tendría que multiplicarse por 4, algo que no permite el algoritmo, aparte que \( 2^{k+1} -1 \) siempre es múltiplo de 3 y como el algoritmo no permite calcular un múltiplo de 3 partiendo desde otro número impar, entonces es imposible.

La misma situación ocurre con los otros 3 patrones que involucran a los demás números impares pues sólo multiplican por 2, por 3 y por 8/3. Entonces, deduzco que el valor del tiempo de detención máximo de cada órbita estaría por debajo del valor del tiempo de detención máximo del \( 2^{k+1} -1 \) inmediato superior de cada número impar.