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í

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

  2. Jorge Novizki dice

    Supongamos una Sucesión en que el último número (lo llamamos U) no fuera 1.
    Supongamos que U fuera PAR. En ese caso, la regla nos permite dividirlo por 2, por lo tanto no es el último número. Llegamos a un ABSURDO.
    Supongamos que U fuera IMPAR. En ese caso, la regla nos permite transformarlo en 3xU+1. Por lo tanto U no es el último número. Llegamos a un ABSURDO.
    Por lo tanto, U debe ser 1.

  3. fernanda dice

    Buenas. En los pocos números que hice, cuando el resultado es 116 inevitablemente se llega al 1. Seguro que hay una ley que lo explique pero no me la acuerdo. Saludos.

  4. Lionel Edgardo Giglia dice

    vi otro error en mi rápido planteo: el punto 2 a) no es cierto, es una burrada. Es más sofisticado cómo se llega a mútiplos de 4. Saludos. Cuando tenga tiempo, me vuelvo a conectar. Gracias.

  5. Lionel Edgardo Giglia dice

    fe de erratas: en la última fórmula para explicar el movimiento descendente de la serie, cometí un error que no cambia el concepto. Cuando digo: «(X.3+1 no llega a compensar la división x4 dado que es menor a (x.3)+x que sería la fórmula de la multiplicación por 4 para cualquier número natural mayor a 1)».
    Lo correcto es. «siendo «Y» un múltiplo de 4, y siendo «X «el resultado de la división por 4 (creo que sería el cociente) , X.3+1 no llega a compensar la división x4 dado que es menor a (x.3)+x que sería la fórmula de la multiplicación por 4 para llegar a Y para cualquier número impar mayor a 1».

  6. Lionel Edgardo Giglia dice

    no se si lo que pensé es un aporte organizador (posiblemente conocido) o una solución, el tema es traducirlo en lenguaje matemático.
    1. la fórmula es un algoritmo simple que transforma un número natural cualquiera mayor que 4, en múltiplo de 4. (por eso, 10 tiene retorno a un número más grande -no es múltiplo de 4 y se transforma en impar- y 16 ya va indefectiblemente a 4.
    2. explicación:
    a) cualquier numero impar x la fórmula de multiplicar x3 y sumar : se transforma en un múltiplo de 4
    b) cualquier número par: si no es múltiplo de 4 al dividirse x2, es impar y x la siguiente fórmula se transforma en múltiplo de 4. Si es múltiplo de 4: vuelve a ser múltiplo de 4 a la segunda operación.
    3. conclusión y problema a resolver: todos los números naturales se transforman en mútiplos de 4 hasta llegar a 4. el único problema formal que queda es resolver por qué la serie es descendente.
    4. resolución: ahí la respuesta que tengo es que tras una multiplicación x3+1, sistemáticamente viene una división x4(2 divisiones x 2), por lo cual la serie tiende sistemáticamente a descender (X.3+1 no llega a compensar la división x4 dado que es menor a (x.3)+x que sería la fórmula de la multiplicación por 4 para cualquier número natural mayor a 1).

    Espero estar en la pista, y si es posible alguna respuesta para seguir pensando, gracias x todo.

    Lionel

  7. Gabriel dice

    Cuatro cuestiones:
    a1. Si n es cualquier número par y se divide por 2, la probabilidad de que el resultado sea también divisible por 2 es 0.5.
    a2. Si n es cualquier número impar y hacemos 3n+1, el resultado siempre es divisible por 2 (probabilidad=1). De modo que, si n es impar, el problema nos lleva, necesariamente, a realizar más cálculos: (3n+1)/2. Ahora sí, la probabilidad de que el resultado de esos cálculos sea también divisible por 2 es de 0.5.
    b1. En cada ronda, cuando n es impar, el resultado menos que duplica n: (3n+1)/2=2n-(n-1)/2.
    b2. En cada ronda, cuando n es par, el resultado es la mitad de n.
    Sirve esto de algo?

  8. Augusto Parma dice

    Cuando se llega a un 2 a la n potencia, la caída hacia el uno es inevitable: ejemplo: 2 a la potencia 10 = 1024

    1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1

  9. Augusto Parma dice

    Los últimos números de la serie obtenida con el algoritmo siempre parecen ser 10, 5, 16, 8, 4, 2 y 1, así que el problema es el maldito número 10.

  10. guillermo dice

    uhh ES HERMOSO!

  11. guillermo dice

    vos, adrian querido, queres una ley que abarque el infinito? mañana me pongo, pero tirame una pista, que libro me compro.

  12. Ernesto Oscar dice

    Querido Adrián, a mis 85 mis luces ya no son las mismas pero, no veo cuál es el problema o como se lo quiera llamar porque cada vez que aparezca un número par hay que dividirlo por 2 y cuando aparezca un impar la «regla» dice que hay que sumarle 1 para transformarlo en par y seguir dividiendo por 2, no importa que número elijamos para comenzar la serie decreciente siempre vamos a llegar a 1. Para mí ni problema ni algoritmo, sólo una trampita.

  13. Rubén dice

    Estimado profesor:
    Como aprendiz de brujo acometí este algoritmo hace un par de años, basando mi hipótesis en elementales conceptos
    de matemática de conjuntos (la misma que prohibieron los militares de la dictadura porque «como se sabe todos los
    conjuntos son subversivos») aprendidos en la secundaria, allá por los 60 cuando era una novedad. Obtuve una conclusión
    en línea con la conjetura, pero lamentablemente no tengo a quien someter a juicio dichas conclusiones, y que me diga
    donde se escapó la liebre.
    Con afecto. Rubén

    1. Raúl dice

      Por favor, podría publicar su solución o intento ? Gracias.

  14. María Costa dice

    Buen día Adrián. Tuve una semana para olvidar. La distancia y la falta de afectos me está afectando mal.
    Más cuando uno desde el interior muy profundo ve los cambios en Buenos Aires y de lo que se escucha o lee, cae de maduro el total y absoluto desconocimiento de lo que pasa por aquí, donde encima gano la oposición y lo único visible es que las únicas personas que conozco quedaron sin renovación de contratos. Es decir, no eran personal de planta, ya ni monotributista.
    Quiero contar de una en particular, profesional que se formó en género, y fue destacada en su participación.
    Hoy el cargo está ahí, con una militante…
    Yo estudié, Educación y Derechos Humanos, tengo todos mis certificados, en ese egoísmo particular docente, como no tengo las materias pedagógicas no me extendieron un analítico ni me dieron el título…ya estaba todo desarticulado. Lo hice en Mendoza, hoy vivo desempleada en Tartagal…fue un milagro recibir todas las certificaciones.
    El punto que quiero cuestionarme a usted, aunque no me responda: vamos a avanzar en género, en ESI, si no hacemos una convocatoria a quienes se formaron en Derechos Humanos.
    O pasará como con las TIC, que hasta el 🐈 se daba por conocedor e insistió siempre en la falta de conectividad, cuando lo importante era la herramienta y todo lo pre cargado en ella.
    Hice el Postítulo en Educación y TIC, maravilloso ya le he contado que desde 2012 a hoy mis ex alumnos siguen en contacto porque descubrimos juntos lo potente de estar vinculados y debatir las problemáticas que los aquejan.
    Si llegó hasta acá, gracias por leerme.
    En 2018, una profesional de la zona me dijo no hay especialistas como vos en TIC, pero igual yo sigo desempleada.
    Saludos, desde Tartagal, si ese donde fallecio6un niño en una comunidad Wichí.

    1. María Inés BT dice

      ¡Qué susto! creí que había una mujera tratando de resolver un problema ajeno.

Dejá tu comentario

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