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.