martes, julio 12, 2016

Jugando con la Conjetura de Collatz

Ayer llegué a través de Twitter a un enlace que habla de la Conjetura de Collatz. Aparece representado como el problema más simple de las matemáticas que aun no ha sido demostrado o desmentido.
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
2^m = n×3^j+sum_(i=j-1)^0 3^i  
donde n y j son dos números naturales, que en nuestro caso representan cualquier número n y j el número de veces que realizamos la operación de multiplicar por 3 y sumar 1.

8 comentarios:

  1. 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.

    ResponderEliminar
  2. La solución es mucho más simple que eso. ;-)

    ResponderEliminar
  3. La demostración, la explicación, la solución, no es otra que la conjetura misma. ;-)

    ResponderEliminar
  4. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  5. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  6. Tal vez la forma más fácil de demostrar la Conjetura de Collatz: https://www.youtube.com/watch?v=nyqSy7171Yg

    ResponderEliminar
  7. Lo 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.

    ResponderEliminar
  8. Oye si te fijas las sumas que haces en el ejemplo están mal desde la segunda iteración, lo correcto sería así:
    101001+1010011=1111100

    ResponderEliminar