Os adjunto el vídeo de Derivando en el que se explica muy bien:
Más información al respecto se puede encontrar en Gaussianos o en la Wikipedia.
Esta mañana me he entretenido en la biblioteca a trastear con la conjetura, llegando a unas conclusiones que a posterior he visto en la Wikipedia. Os cuento cómo he llegado a ellas y cómo desde ahí la conjetura se puede formular en otros términos, quizás más accesibles para su demostración/negación.
Según la conjetura, cualquier número bajo las reiteradas operaciones de:
- en caso de ser par, división por 2
- en caso de ser impar, multiplicación por 3 y al resultado se le suma 1
termina llegando a 1.
El algoritmo de estas operaciones se simplifica si utilizamos la representación binaria de números puesto que:
- en el caso de los pares, la división por 2, significa quitar el último cero (ejemplo 18 (10010) entre 2 es 9(1001).
- en el caso de los impares, la multiplicación por 3 y sumar después 1 pasa a ser la suma del número en binario más ese mismo número al que se le añade un 1 al final (ejemplo 9 por 3 y luego sumado 1 resulta 28 que en binario se realizaría como 1001 + 10011= 11100).
Un resultado obvio es que, siempre después de un número impar va a salir un número par, así que todo operación de multiplicación por 3 más 1, siempre viene acompañada de una posterior división por 2.
Si uno estudia por encima en qué momento termina el número colapsando a 1 irremisiblemente, se dará cuenta de que eso ocurre SOLO en el momento en el que las operaciones le han llevado a una potencia de 2. En ese momento, operaciones consecutivas de división por 2, llevarán el número a 1.
Para lo que voy a explicar a continuación, es importante saber que todas las potencias de 2 en binario tienen la forma de un 1 seguido de una cierta cantidad de 0s (ejemplo: 8 (1000) ; 64 (1000000); etc).
Ya que dividir por 2 solo quita ceros al final, podemos reformular el algoritmo de cálculo a una sola operación:
independientemente de si es par o impar, se le quita todos los ceros que tenga la final y al número resultante, se le suma ese mismo número añadiendo un 1 al final.
Con este algoritmo podemos calcular las iteraciones más deprisa. Por ejemplo, mientras que el número 27 requiere de 111 pasos en notación decimal, con este algoritmo se realiza en:
27 (11011) ->
11011 + 110111 = 101001
101001+1010011= 1011110
101111+1011111= 10001110
1000111+10001111=11010110
1101011+11010111=101000010
10100001+101000011=111100100
1111001+11110011=101101100
1011011+10110111=100010010
10001001+100010011=110011100
1100111+11001111=100110110
10011011+100110111=111010010
11101001+111010011=1010111100
10101111+101011111=1000001110
100000111+1000001111=1100010110
110001011+1100010111=10010100010
1001010001+10010100011=11011110100
110111101+1101111011=10100111000
10100111+101001111=111110110
11111011+111110111=1011110010
101111001+1011110011=10001101100
100011011+1000110111=1101010010
110101001+1101010011=10011111100
100111111+1001111111=1110111110
111011111+1110111111=10110011110
1011001111+10110011111=100001101110
10000110111+100001101111=110010100110
11001010011+110010100111=1001011111010
100101111101+1001011111011=1110001111000
1110001111+11100011111=101010101110
10101010111+101010101111=1000000000110
100000000011+1000000000111=1100000001010
110000000101+1100000001011=10010000010000
1001000001+10010000011=11011000100
110110001+1101100011=10100010100
101000101+1010001011=1111010000
111101+1111011=10111000
10111+101111=1000110
100011+1000111=1101010
110101+1101011=10100000
101+1011=10000
1
un total de 40 pasos.
Bajo esta perspectiva, demostrar la conjetura de Collatz equivaldría a demostrar que el desplazamiento de los números binarios bajo la operación arriba indicada, aplicada una cierta cantidad de veces, lleva ineludíblemente a 1. Según lo veo yo, hemos pasado de un problema de Teoría de números a uno de Traslaciones en un espacio n dimensional.
------------------------------------------------------------------------------------------
A partir de lo anteriormente dicho, y obviando la operación de división por 2 (como hemos comprobado que se puede hacer), llegamos a que los sucesivos números que se obtienen son de la forma:
Con lo que otra manera de reformular la conjetura es decir que cualquier potencia de 2 se puede escribir como
Has llegado prácticamente a las mismas conclusiones que yo, pero has cometido el mismo error que yo cometí en un primer momento. En la sucesión, en el n2=n1+1, el 1 no es tal. Sería el primer uno en la cadena de unos y ceros (sería el equivalente a quitar los ceros), por lo que si el número tiene los siguientes unos y ceros: 1.....1000, el siguiente sería n*11+1000 en binario. La dificultad está en representar en la sucesión ese 1000 en binario.
ResponderEliminarLa solución es mucho más simple que eso. ;-)
ResponderEliminarLa demostración, la explicación, la solución, no es otra que la conjetura misma. ;-)
ResponderEliminarEste comentario ha sido eliminado por el autor.
ResponderEliminarEste comentario ha sido eliminado por el autor.
ResponderEliminarTal vez la forma más fácil de demostrar la Conjetura de Collatz: https://www.youtube.com/watch?v=nyqSy7171Yg
ResponderEliminarLo que se necesita demostrar no es si el algoritmo conduce a 1 pues es algo obvio que si tomas un impar y lo conviertes a par y luego lo pasas dividiendo vas a llegar a 1, es parecido a descomponer en factores. Lo que se pregunta en la conjetura es si siempre llega a 1, es decir si no existe un ciclo que tenga pasos infinitos que nunca permitan llegar a 1 o que exista un ciclo que caiga en un bucle infinito distinto a 4, 2, 1, 4, 2, 1, 4, 2, 1. Esta exposición está orientada hacia lo primero y no hacia lo segundo, por lo tanto la exposición sólo nos devuelve a la misma conjetura.
ResponderEliminarOye si te fijas las sumas que haces en el ejemplo están mal desde la segunda iteración, lo correcto sería así:
ResponderEliminar101001+1010011=1111100