El algoritmo de Siracusa 

Un problema histórico que aún busca solución

 

Le propongo que construyamos juntos una sucesión de números naturales (enteros positivos). La regla es la siguiente: empezamos por uno cualquiera. Digamos, a manera de ejemplo, que elegimos el número 7. Ese va a ser el primer elemento de nuestra sucesión.

Para generar el segundo elemento, hacemos lo siguiente: si el que elegimos primero es par, lo dividimos por dos. En cambio, si es impar, lo multiplicamos por 3 y le sumamos 1.

En nuestro ejemplo, al haber elegido el 7, como no es par, tenemos que multiplicarlo por 3 y sumarle 1. Es decir, se obtiene el número 22, ya que 3 x 7 = 21 y sumando uno, queda 22.

Ahora bien: tenemos entonces los primeros dos elementos de nuestra sucesión: {7,22}.

Para generar el tercer número de la sucesión, como el 22 es un número par, lo dividimos por dos, y obtenemos 11. Ahora tenemos {7,22,11}.

Como 11 es impar, la regla dice “multiplíquelo por 3 y súmele 1”. O sea, 34. Se tiene {7,22,11,34}.

Luego, como 34 es par, el próximo elemento de la sucesión es 17. Y el siguiente es 52. Luego 26. Y después 13. Y sigue 40. Luego 20. Hasta acá tenemos {7,22,11,34,17,52,26,13,40,20}.

Seguimos dividiendo por dos los pares y multiplicando por 3 y sumando 1 a los impares: {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}. Y en el número 1, paramos.

Lo invito ahora a que elijamos cualquier otro número para empezar, digamos el 24. La sucesión que se tiene es: {24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1}.

Si ahora empezamos con el 100, se sigue: {100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}.

Como se alcanza a ver, todas las sucesiones que elegí terminan en el número 1. En realidad, aunque no lo dije antes, al llegar al número 1 el proceso se detiene, porque si uno siguiera, entraría en un lazo, ya que del 1 pasaría al 4, del 4 al 2 y del 2 otra vez al 1. Por eso es que cuando al construir la sucesión llegamos al número uno, detenemos el proceso.

Hasta hoy, noviembre del 2019, en todos los ejemplos conocidos siempre se termina la sucesión en el número 1. Pero, no se tiene ninguna demostración que pruebe que el resultado es válido para cualquier número. Este problema se conoce con el nombre del “Problema 3x + 1”, o también como el “Problema de Collatz”, o “Problema de Siracusa”, o “Problema de Kakutani” o “Algoritmo de Hasse” o “Problema de Ulam”.

Como ven, tiene muchos nombres, pero ninguna solución. Es una buena oportunidad para empezar. Con todo, es poco probable que a un “lego” se le ocurra cómo resolver el problema general. Pero, en la historia de la humanidad hay múltiples ejemplos de personas que tuvieron el ingenio suficiente para superar dificultades para la que se suponía que no estaban preparadas. Y lo hicieron, casi sin historia en el área ni herramientas sofisticadas.

 

 

 

--------------------------------

Para suscribirte con $ 250/mes al Cohete hace click aquí

Para suscribirte con $ 500/mes al Cohete hace click aquí

Para suscribirte con $ 1000/mes al Cohete hace click aquí

20 Comentarios
  1. Soy Alexander Villarroel de Venezuela, Muy pronto abriré mi canal de youtube donde hablaré de temas y problemas pendientes y polémicos de las matemáticas, luego de la presentación comenzaré por la conjetura de collatz con lo conocido desde 1937 hasta la actualidad y luego presentaré mi demostración. En el programa iré explicando los procedimientos que segui. Espero su atención. Cerraré con esa serie de programas con la presentación de mi fórmula de iteraciones. Saludos. Espero me vean desde el viernes 24-07-2020. El programa será muy interesante. Le escribí al señor Paenza solicitando su ayuda, a través del twitter pero no obtuve respuesta de su parte.

  2. mariano dice

    Hola. Entiendo que usted es un matemático y teniendo esto en cuenta le pido me explique cual seria la incognita. No encuentro un problema a resolver.. Entiendo que cualquier numero natural impar multiplicado por 3 me va a dar por resultado otro número impar. ¿Esto es correcto? si asi fuere y a este resultado le sumase 1 entonces tendria un numero natural par.
    Entiendo que siguiendo el planteo propuesto cuando el resultado no fuere divisible por 2 al sumarle 1 entonces inevitablemente lo hago y siguiendo esta lógica siempre voy a derivar en uno. No entiendo cual es el objeto a decifrar. Agradeseria me ilustre.
    Lo saludo atte:

  3. guillermo dice

    Bueno Adrian, me harte. Aun que descubri muchas cosas curiosas y fascinantes (que odie y ame saber que las pensaron griegos antiguos y peruanos pelotudos antes que yo) la solución se puede ver pero no alcanzar, y en todo caso alcanzarla de esta forma seria como hacer un mapa del mundo del mismo tamaño del mundo. Inútil.

  4. Santiago Aon dice

    Adrián, conocí este problema en uno de tus libros, desde ese momento se convirtió en prácticamente una obsesión que cada tanto retomo.
    Me tomo el atrevimiento de aventurar, aunque cabe la posibilidad que esté incurriendo en una subestimación del problema, una posible explicación matemática al hecho de que partiendo de cualquier valor se caiga indefectiblemente hacia el 1.
    La cuestión sería la siguiente: tomando un X0 cualquiera, si este es de condición impar inmediatamente cae hacia un número par; si en cambio fuese un número par, no sabemos cuántos mapeos pares le tomará a ese número (depende de su grado de paridad, por definirlo de alguna manera), pero indefectiblemente en algún momento caerá hacia un nuevo número impar.
    De esta manera podríamos decir que bastaría con restringir el análisis a aquellos X0 impares dado que todos los pares quedarían vinculados, aunque de una manera menos explícita, al análisis.
    La función que definiría a la conjetura podríamos expresarla como: (3^f)*X0+k=(2^t)*Xei, siendo X0 el valor inicial, Xei el valor al que se arriba (consideremos a ambos impares), el coeficiente f la cantidad de mapeos impares que existen entre X0 y Xei, t la cantidad de mapeos pares existentes entre X0 y Xei y k la acumulación que surge de los términos +1 producto de los mapeos impares.
    Suponiendo una sucesión de valores del tipo X0; F(X0)=X1a; a*T(X1a)=X1i; F(X1i)=X2a; b*T(X2a)=X2i; F(X2i)=X3a; c*T(X3a)=X4i… e*T(Xea)=Xei
    De esta manera vemos que t=a+b+c…+e). Veamos ahora la evolución de cada término de la función original en cada tipo de mapeo.
    Para los mapeos pares tomemos por ejemplo la relación entre X2a y X2i, pero siempre considerando Xo como punto inicial. La función quedaría definida como (3^f)*X0+k=(2^t)*X2a.
    Independientemente de la cantidad de mapeos pares existentes entre X1i y X2i (definido anteriormente como b), los mapeos pares no alteran al término (3^f)*X0 ni al término k, solo producen una transferencia de grados de paridad de X2a hacia t. Lo que podríamos definir como volumen de la función se mantendría constante (incluso este último término se mantendría constante, dado que solo se modificaría cualitativamente).
    Para los mapeos impares podemos considerar la sucesión en toda su magnitud.
    En dichos mapeos, en cambio, se produce una variación en el volumen de la función cuyo rango de variación tiene límite inferior en 3/1 (para valores de X0 cercanos al infinito la incidencia del término +1 producto del mapeo impar sería casi nula pero nunca igual a 0) y un tope máximo en 4 (para X0=1 la variación sería de 4/1 veces X0). De esta manera, el término (2^t)*Xei puede variar dentro de un rango de entre 3 (como límite) y 4 veces con cada mapeo impar. La variable que toma dicha variación es, obviamente, Xei.
    Del otro lado de la función, la variación en el término (3^f)*X0 es constante e igual a 3, dado que solo el exponente f puede variar. Por lo tanto el término k debe compensar la diferencia de variaciones entre los término (3^f)*X0 y (2^t)*Xei.
    Ahora, la variación del término k para el segmento X0->X1i, podríamos denominarlo k(Xo->X1i) es simplemente +1. En términos de su incidencia respecto del acumulado en el término (3^f)*X0 sería de 1/(3*X0).
    Su variación para el segmento X0->X2i, o lo que es lo mismo k(X0->X2i)=3*k(X0->X1i)+(2^a), con lo cual su incidencia respecto del acumulado de (3^f)*X0 sería de 3+(2^a)/(9*X0)
    Respecto del segmento X0->X3i, o sea k(X0->X3i)=3.k(X0->X2i)+(2^b). Siguiendo lo anteriormente planteado su relación respecto del acumulado de (3^f)*X0 sería de 9+3*(2^a)+(2^b)/(27*X0).
    Tal como puede observarse, la incidencia del término k en el lado izquierdo de la función es cada vez mayor, dado que el término (3^f)*Xo solo puede crecer de manera constante y el término k crece no solo influido por la multiplicación por 3 sino que además suma la cantidad de exponentes pares existentes entre los dos últimos X impares.
    Dicho de otra manera, k(X0->X3i)/(3^3)*X0 > k(X0->X2i)/(3^2)*X0 > k(X0->X1i)/3*X0.
    Si k tiene una evolución más rápida que el término (3^f)*X0, pero este a su vez evoluciona de manera constante e igual a 3, implica que todo el lado izquierdo de la función evoluciona de manera cada vez más próxima a 4 y, tal como mencioné anteriormente, si el volumen de la función tiende a evolucionar a un ritmo de 4 veces en cada mapeo impar, esto quiere decir que la función está aproximándose no hacia un Xei infinito sino hacia un Xei=1.
    Entiendo que debería demostrarse, asimismo, que solo Xei=1 permite caer en rulos que produzcan re-iteraciones de si mismo. Esto es bastante simple de demostrar cuando f=1, ya que si Xo=Xei entonces la función quedaría definida como 3*X0+1=(2^t)*X0, por lo tanto 3+(1/X0)=2^t.
    Dado que 2^t debe pertenecer a los naturales, para cualquier valor de X0 diferente de 1, 2^t debería tomar valores fraccionarios en un rango de entre 3 y 4. Por lo tanto solo X0=1=Xei.
    De todas maneras habría que buscar maneras de resolver el problema cuando f es diferente de 1 (cuando existen varios mapeos impares entre dos valores que intentemos re-iterar).
    Conozco mis limitaciones y calculo que algo (buena parte o todo) de todo esto puede estar sujeto a errores graves, o a subestimaciones del problema en cuestión, de todas maneras me tomo el atrevimiento de hacértelo llegar.
    Te agradezco tus columnas dominicales, son una incitación a la abstracción.
    Saludos cordiales.

  5. Lionel Edgardo Giglia dice

    Soy psicólogo y sólo le pude dedicar un tiempo en vacaciones a este problema, llegando a algo que puede ser un aporte o quizás haya sido algo transitado. Parto de la hipótesis de que la fórmula produce en la serie, múltiples de 4.
    Paso a exponerlo brevemente:
    1) mientras el nºnatural (llamemosle N) sea múltiplo de 4 a partir de la división por 2, sigue su curso descendente hasta 1.
    2) en caso contrario, entra en la combinación de las 2 fórmulas a partir de un número natural impar:
    el número impar puede ser definido como un múltiplo de 4 + 1 (desarrollaremos consecuencia en caso a) o como un múltiplo de 4-1 (lo desarrollaremos en b). Esto cubre el universo de números impares naturales, entonces, tomando a x = número natural:
    a) si N=(4x+1) , implica que 3(4x+1)-1= 12x+4, lo cual es múltiplo de 4 y vuelve al caso 1. Si sólo existiera esta posibilidad de impar, se llegaría a 1, dado que en la secuencia se multiplicaría x3+1 y se diviría al menos x 4.
    b) si N= (4x-1), implica que 3(4x-1)-1= 12-2, lo cual no da múltiplo de 4 y en la aplicación de la fórmula completa (3N+1), el orden es ascendente.
    3) Entonces, reducimos el problema al N= impar del caso 2 b) dado que es el único caso que la serie No desciende a 1 en principio .
    Acá llegué a lo siguiente:
    a) hay un Límite a la serie indefinida de repeticiones del caso 2.b) de N=(4x-1):
    siempre se produce un múltiplo de 4 (y rompe la repetición recurrente en dividir una sola vez por 2) bajo la siguiente fórmula:
    para todo X: x= 2 (a la n) + 2 (a la n-1) se produce el múltiplo de 4 al aplicar la fórmula (3 N+1)/2 n+1 veces.
    (cuando escribo (a la n) significa potencia y es porque no tengo posibilidad de introducir el símbolo de potencia en este mail)

    4) una hipótesis que no tengo forma de demostrarla para todos los casos, y es lo que queda a determinar es si ese «n» de la potencia da otro límite a la posibilidad ascendente de la serie:
    a) que en todos los casos 2b) que se produzcan en esta serie que parte de este «n», no se superará dicho «n» en la producción de múltiplos de 4.
    b) si esto es así y se puede formalizar, quedaría resolver dentro de cierto «n» cómo se produce la relación de los caso 2.b) que se produzcan u los múltiplos de 4.

    Espero que sea de utilidad

Dejá tu comentario

Su dirección de correo electrónico no será publicada.