Friday, March 08, 2013

Otro reto con la conjetura de Collatz


La conjetura de Collatz es muy sencilla y cualquiera puede entenderla: elíjase un número entero positivo. Si es par, divídalo entre dos; si es impar, multiplíquelo por 3 y súmele uno. A ese resultado proceda de la misma manera. Así, si tomamos, por ejemplo, el número 10, tendremos que es par, entonces dividiremos entre 2, lo cual nos da 5. A ese resultado, multipliquemos por 3 y sumémosle 1. Tendremos como resultado 16. Como es par, entonces tendremos 8, siendo par este dividimos de nuevo entre dos y obtendremos 4. Hacemos de nuevo la división y hallamos 2. Dividamos de nuevo y obtendremos 1. Decimos entonces que 10 es un número maravilloso o de Collatz.

Llegar a probar que 10 es maravilloso lleva 6 pasos: 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1. El número 27, por ejemplo, requiere de 111 iteraciones antes de llegar a 1 y es el número de más iteraciones menor de 50. Cuando John Conway (el creador del juego de la vida) explica la conjetura pasa al pizarrón y dice: "veamos qué pasa si usamos un número al azar… digamos 27"…

Se me ha ocurrido un reto de programación, el cual es hacer un programa que nos diga cuál es la secuencia más larga para llegar a 1 -en la conjetura de Collatz, desde luego- que tienen los números del 1 a un millón. El resultado que el programa debe otorgar es cuál número, en el intervalo [1 .. 1,000,000] tiene la secuencia más larga. Cabe decir que hay dos premios fastuosos: una tarjeta SD de 4 GBytes y una taza con el logotipo de La_Morsa. El programa que llegue al número con la secuencia más larga en el menor tiempo posible, se llevará uno de esos premios (eso lo decide el ganador). El segundo lugar, es decir, el segundo mejor tiempo que llegue a la respuesta correcta, se llevará el premio sobrante. Cabe señalar que los programas que se remitan a mi cuenta de correo deben tener el código fuente y las instrucciones precisas para que los pueda probar. Habiendo tantos compiladores y diferentes sistemas, deben decirme qué hacer para compilar y correr el código a concurso (añadiendo una copia del ejecutable).

Así que a afilar sus armas. A programar y a optimizar. Veamos qué dicen nuestros programadores. Yo ya escribí mi propia versión para resolver este problema. A quien le interese el software, puede pedírmelo a morsa@la-morsa.com y a vuelta de correo tendrá el enlace para descargarlo.

13 comments:

Orochi said...

Mmm me animaría... pero se me hace que ya lo intenté en una de sus clases y fracasé... los números maravillosos... que recuerdos... mmm igual y en php es sencillo jejeje

Orochi said...

¿No ya lo habiamos intentado en clase en prolog profesor? me suena a que sí

emiliano said...

Y para que quiere el codigo fuente? No quiere tambien una nieve de limon, digo ya que se trata de pedir?

emiliano said...

Y para que quiere el codigo fuente? No quiere tambien una nieve de limon, digo ya que se trata de pedir?

Morsa said...

Emiliano,

Déjame explicarte:

1. El concurso trata de una conjetura en matemáticas que se describe muy fácilmente en términos de cómputo. No estoy pidiendo un algoritmo hipercomplejo, o algo que simplemente sea lleve semanas o meses para programar. Es un algoritmo de diez líneas, no más.

2. Pido el código fuente porque por una parte, puedo recompilarlo y ver que efectivamente hace lo que el concursante dice que hace. Por ejemplo, en el caso que nos ocupa, alguien podría darme un programa que desplegara el resultado sin hacer cálculo alguno y si no tengo el fuente, tengo que creer que el programador hace muy, pero muy rápido, toda esa cantidad de cálculos. Así, por una parte, sirve para corroborar que quien gane de verdad hizo la tarea encomendada.

3. El programador, quizás no lo sepas, aprende de lo que otros escriben. Nadie inventa todos los algoritmos y por eso es importante la parte de compartir con los dmeás el código. Hay gente que cree que tiene derechos sobre el código que escribe y es su punto de vista. En mi opinión, la tendencia es que el código sea abierto, porque así todos podemos aprender de los demás. Y así nos retroalimentamos.

4. Por último, el reto planteado es un mero divertimento que se hace en un rato. No te llevará ni días, semanas o meses. En un par de horas las cosas están funcionando.

5. Si yo pidiese el código fuente para sacar ventaja de algo, para hacer un trabajo que no he hecho, por ejemplo, bien podrías recriminármelo, pero en este caso el reto es tan simple que ocultar el código fuente es un poco fuera de lugar.

6. Por último, si no te parece entregar el código fuente, pues no participas en el reto y ni modo. Nos perderemos de tu contribución.

saludos
Manuel

Francisco said...

Si, es bastante simple y directo. Ya lo tengo. A lo mejor lo más interesante va a estar en qué estrategias se ocurren para optimizar. Ya nos platicarás, pero el cálculo directo, bruto es bastante rápido.

No voy a participar porque lo hice en una macro de Microsoft Excel, una hoja de cálculo ampliamente utilizada en el mundo corporativo, pero que es bastante, bastante lenta para este tipo de operaciones. Estoy seguro que casi cualquier otra cosa va a ser más rápida, pero es lo único que tenía a la mano. El cálculo bruto en esta plataforma toma como 15 secs.
Ah, por cierto, aprendí que la función "Modulo" de Excel tiene un "bug" y truena con números muy grandes... Parece que ya se han dado cuenta de esto desde hace varios años pero las nuevas versiones siguen con este defecto. Es que en realidad Excel no está pensado para este tipo de cosas.

Conoces alguna plataforma de programación que sea gratis o barata y adecuada para cálculos numéricos pesados? Tengo algunas ideas que datan de mis tiempos de científico que no terminamos de explorar y que me gustaría retomar.

admin said...

¿El tiempo más rápido incluye la compilación del programa? hay una técnica de programación en C++ (template metaprogramming, buscar en wiki) que nos permite hacer los cálculos en la compilación, de esta manera, al momento de correr el programa compilado, nos mostraría inmediatamente la respuesta siempre.

Bueno, como buen ejercicio de programación, lo hice así, pero aún lo estoy puliendo.

Uziel García said...

Que ese no es el problema 14 de projecteuler?

Morsa said...

Así es, está sacado el problema de esa página.

saludos

Morsa said...

Francisco, ¿una herramienta específica para estas cuestiones smatemáticas que sea gratuita y libre de costos? No sé, pero busqué en la red y ahllé esto: http://stackoverflow.com/questions/33550/best-open-source-mathematica-equivalent

Busqué mathematica clone free y da montones de resultados.

saludos
Manuel

Morsa said...

admin, sólo hablo de tiempo en hallar la secuencia más larga. No que compile más rápido.

saludos
Manuel

Morsa said...

sí, 15 segundos es una vida en este problema, Francisco. Mañana aparecerán publicados los resultados.

saludos
Manuel

Bernardino tanarro said...

¿hasta cuando se puede participar en este reto?. No he tenido mucho tiempo y quizas mañana participe