Collatz

[Spazski]

He de admitir que nunca me paso por este subforo...

Las matemáticas siempre me han gustado, y estos problemillas o curiosidades me intrigan. Además programo con MatLab, así que he podido seguir bastante bien todo el hilo. Lo que más me cuesta es el lenguaje de programación, más parecido a C+ o Java, que en absoluto conozco.

Es lógico pensar que cualquier número impar al que le sumes uno, se convierte en par; y que cualquier número impar multiplicado por 3 sigue siendo impar (por descomposición en factores); si se pudiera demostrar que la "velocidad" de crecimiento de 3*n+1 es menor que la de decrecimiento de n/2 para cualquier "n", entonces la regla es siempre cierta.

Jetro, quería hacerte una observación acerca del tiempo de órbita, como lo llamas. No lo he pensado demasiado, es más bien una corazonada (tengo un examen el martes, no estoy para pensar en exceso), pero te lo comento por si quieres pensarlo o esperar a que en 3 días lo piense yo mejor.

Si reconstruyo el problema a la inversa (es decir, partiendo de "1"), y lo multiplico por 2 constantemente (pues todo número resulta par, por lo que no puedo salir del ciclo), obtengo todas las potencias de 2 (que, al ser potencias de 2, quizás pudiera esta conjetura tener una aplicación en el código binario, que ahora mismo no viene al caso). El caso es que, desde una potencia de 2, el tiempo de órbita se reduce drásticamente, pues siempre hay que dividir por 2, haciendo decrecer el número siempre. Si diseñas una serie de operaciones que lleven desde un número hasta una potencia de 2, habrás resuelto un problema similar en poco tiempo. Lo que me lleva a pensar que las operaciones de Collatz transforman al número en una potencia de 2 al final (mayor o menor, tardando más o menos). Entonces podría ser interesante estudiar la convergencia de las transformaciones a una curva de las potencias de 2. No tengo muy claro cómo verlo gráficamente...

No se por qué, pero me viene a la cabeza una espiral de valores aproximándose a una curva de potencias de 2. Podría asemejarse a un problema dinámico en el que tenemos una posición inicial X (el número), y una velocidad inicial V (propiedad del número) que nos indica en qué dirección va a avanzar, además de una aceleración A (otra propiedad del número) que vuelve a modificar la trayectoria.

No se si me he conseguido explicar. Es algo más matemático y de análisis de resultados que de programación.

Con esos datos, podrías predecir el tiempo de órbita de cada número, o si el máximo número que aparecerá en su tratamiento estará dentro de una cota o de otra.

Gran trabajo Jetro ;) Siento el tocho que he soltado...

[Jetro]

Tranquilo que yo también tengo la cabeza bastante nublada, aunque en mi caso por falta de sueño.

Lo que dices suena bien, pero no acabo de ver cómo encajarlo. A primera vista parece que las potencias de dos tienen relativamente poca incidencia en los números Collatz. Si observas la secuencia en el poster que hice (en este mensaje) en el que de hecho calculé los números al revés, verás que hasta 16 todo son potencias de 2, pero después de eso solo 7 de los 32 resultados son potencias de 2 y solo en cada segundo paso sale un ramal impar (64 -> 21, 256 -> 85, 1024 -> 341) y a partir de allí la distancia a la potencia de dos es cada vez mayor...

Bueno, suficiente, que espero tu elaboración sobre el tema porque igual me estoy yendo por un lado completamente diferente a lo que tienes en mente...

[Spazski]

Hoy he tenido un examen que me ha exprimido los sesos, así que no estoy demasiado lucido.

Con Collatz tenemos 2 opciones: disminuir el número dividiendo por 2, o aumentarlo multiplicando por 3 y sumando 1. Si queremos llegar hasta "1", lo que tenemos que hacer es disminuir el número. La única operación para disminuirlo es dividir por 2 una y otra vez, hasta obtener un número impar. Entonces, el número más óptimo para llegar lo antes posible al resultado "1" es cualquier potencia de 2, ya que puedes dividir una y otra vez por 2 hasta llegar a "1".

Por eso, antes de llegar al número "1", tendremos que caer por fuerza en una potencia de 2, a partir de la cual caemos en picado hacia el "1".

Entonces podríamos decir que multiplicar por 3 y sumar 1, así como dividir por 2, es todo una "maniobra de aproximación" hacia una potencia de 2.

Si caemos en una potencia de 2, es porque veníamos de un número impar (si fuera par, sería entonces 2*2^n=2^(n+1), por lo que sería una potencia de 2). Entonces tenemos que: 2^n=3*x+1  ==> x=(2^n-1)/3  Esta relación sólo se puede cumplir para unos valores determinados de "n", lo que nos indica que tenemos restringidas las "entradas" a la curva de potencias de 2. Haciendo unas pruebas sencillas:

n=1 --> x=0.33 --> NO
n=2 --> x=1 --> Sí, pero no nos vale porque es el objetivo final: alcanzar el 1; ¡no podemos venir de él!
n=3 --> x=7/3 --> NO
n=4 --> x=5 --> SI
n=5 --> x=31/3 --> NO
n=6 --> x=21 --> SI
n=7 --> x=127/3 --> NO
n=8 --> x=85 --> SI
n=9 --> x=511/3 --> NO
n=10 --> x=341 --> SI

En conclusión se puede ver que sólo podemos "entrar" en las potencias pares de 2, proveniendo de un número impar (al que hemos llamado X ). A su vez, este número impar proviene de un número par irremediablemente (al que llamaremos Y ). ¿Por qué? Porque la "regla" para saber si un número es divisible entre 3 es que la suma de sus cifras sea múltiplo de 3; y si tomamos el número divisible entre 3 y le restamos 1, hacemos que sus cifras dejen de sumar un múltiplo de 3. Además sabemos que cualquier número no divisible por 2, tampoco lo es al multiplicarse por 3 (por simple descomposición en factores). Luego no puede provenir de un número impar.

Y ahora empieza el bucle...

Este número par Y puede provenir de un número impar, o de uno par. Si proviene de unos par, es de la forma Y*2. A su vez, este número puede provenir infinitamente de número pares de la forma Y*2^n, que es una nueva potencia de 2, pero multiplicada por una constante. También puede que este número Y provenga de un número impar (al que llamamos Z) de la forma Y=3*Z+1.

Y lo mismo ocurriría con Z.

Entonces podemos pensar que partimos de un número al que podemos descomponer en un número impar multiplicado por una potencia de 2. Es decir: X=K*2^n, siendo K el número impar. Dividiremos entonces por 2 un número de veces igual a "n", y alcanzaremos el valor K. Como no podemos seguir dividiendo por 2, aplicaremos la otra operación: 3*K+1. Este nuevo número volverá a ser parte de una potencia de 2, de la forma W*2^n, donde W es el nuevo número impar. Repetiremos esta operación una vez tras otra, hasta conseguir que el número impar que multiplique a la potencia de 2 sea igual a "1", nuestro objetivo final.

Así pues, y por fin termino, podemos ver gráficamente como saltamos de un punto a una potencia de 2, y bajamos por ella hasta su punto más bajo; entones volvemos a saltar a otra potencia de 2, la cual volvemos a recorrer hacia abajo hasta su punto más bajo. Y así hasta caer en la potencia de 2 básica: 2^n, cuyo punto más bajo es "1".

Una idea gráfica:


¡Menudo lío! Ahora se podría estudiar el número inicial K, para saber cuánto tardaríamos en llegar hasta "1".

¡Un saludo!

[31415926]

Muy bueno Spazski :}, se nota que con los exámenes la mente trabaja muy bien, por favor sigue.

Este problema da mucho que hablar, hasta suena http://www.youtube.com/watch?v=EEdrNmJ0Euk

Y tras una generalización a los complejos nos genera un fractal
La función es equivalente a F(x) = (1+(-1)^x)x/₄ + (1-(-1)^x)(3x+1)/₂
Reemplazando (-1)^x por cos(x*Pi) y simplificando F(x) = (2+7x-(2+5x)cos(x*Pi))/₄
Es una función que podemos iterarla sobre los complejos y analizarla como un fractal

en http://en.wikipedia.org/wiki/Collatz_conjecture

[Jetro]

Voy a tener que leer esto alguna vez más pero voy viendo a lo que quieres llegar.

Lo del fractal... no sé cómo se me ha pasado ... :D

[mrquesito]

¡Imresionante! Para que digan que los Legos es un hobby sin aplicaciones prácticas. Gran trabajo, yo también me he puesto a experimentar un poco con la conjetura de este señor, y he encontrado algo curioso: en números consecutivos, hay una tendencia a converger a partir de cierto número. Por ejemplo, 78 y 79; 118 y 119; 156, 157 y 158; 178 y 179; 236, 237 y 238; 246, 247; 268, 269; 278, 279; 256, 257 y 258; 556, 557, 558; 656, 657 658, 659 terminan por converger en el número 304 (que he encontrado completamente al azar). Resulta curioso que, por ejemplo, aparezcan los números:

• 156, 157 y 158
• 256, 257 y 258
• 556, 557 y 558
• 656, 657 y 658

Se omiten algunos números, concretamente cuando el número de las centenas es 0, 3, 4, 5, pero estos convergen en otros números. Pero si se examinan a fondo, todos los números que terminen por 56, 57 y 58 acaban por coincidir en sus últimas iteraciones: 40, 20, 10, 5, 16, 8 4, 2, 1.

No creo que sirva de mucho, pero me ha saltado a la vista al echarle un vistazo a los 91 folios de iteraciones que he calculado (hasta el 1000  X) )

Muy instructivo, sí señor.

[Vi]

Holas;

A esto le llamo yo "quedarse contento"  :D
[....]

Pozí....  :D

Jetro, habrás quedado a gusto....  :angel:

Muy bueno todo el trabajo realizado. De todas formas, esto de Lego tiene poco: no hay bricks, sólo has usado el NXT, pero como máquina de cálculo. Curioso, el 9232, ¡qué tendrá....?

Ojo, Jetro, en la leyenda del póster has puesto 3n-1 para los impares, cuando ha de ser 3n+1 según tu primer mensaje.

[Jetro]

Ojo, Jetro, en la leyenda del póster has puesto 3n-1 para los impares, cuando ha de ser 3n+1 según tu primer mensaje.

Si, algunos mas me llamaron la atención sobre eso y lo he corregido en el original... solo que en el primer mensaje no - me sirve para ver si realmente lees lo que escribo  X) B)