Collatz

[Jetro]

Concepto:

Si no tienes ni idea de qué va el título, tranquilo. Tampoco lo tenía yo, pero en esta vida se aprende algo todos los días. Hace unos días, leyendo la tira cómica de una página que me suele gustar me encontré con esto:

La verdad es que, aunque las clases de mates eran mortalmente aburridas,  siempre me han intrigado los puzles matemáticos y este es bastante curioso. Se trata de la conjetura Collatz, llamado así por Lothar Collatz, matemático alemán quien al parecer fue el primero en postular la conjetura, aunque la misma lleva varios nombres más (Ulam, Kakutani, Thwaies, Hasse, Syracuse...). Finalmente se le conoce por el nombre más genérico: 3n+1

Para los que prefieren fórmulas:

La conjetura es la siguiente: comienza con cualquier numero natural (un entero positivo). Si el número es par se divide entre dos, si es impar se multiplica por tres y se añade uno. Repite el proceso ad infinitum. Independientemente del número que elijas, finalmente llegarás a 1.

Aunque hasta ahora se ha demostrado por fuerza bruta que la conjetura es correcta en todos los números naturales hasta 20 × 2⁵⁸ no se ha demostrado que sea cierta.



Aplicación:

Pasemos a la práctica. MINDSTORMS no solo es una plataforma excelente para robots sino también para aprender algo de programación (indispensable para la creación de robots) y esta es mi primera incursión en este campo.

Cuando ya tenía una idea general de cómo quería implementar esta conjetura en un programa (no tanto por el cálculo en sí, sino más bien por la interfaz de usuario que lo acompaña) me dio por mirar si alguien ya había tenido l misma feliz idea en NXTLOG. ¡Craso error! Brian Davis hizo un programa llamado Hailstones (otro de los múltiples nombres de esta conjetura) que es una maravilla de sencillez de uso y contenido en bloques muy aprovechables.  Por un momento estuve tentado de abandonar, pero decidí modificar mi interfaz de entrada y aprovechar algunas de las excelentes ideas que se encuentran en ese programa: MyBlocks tan útiles como "Modulo" o un bloque que te permite escribir un número con su correspondiente etiqueta en una línea determinada o llenar la pantalla de texto con un solo bloque.
Otra excelente idea es el bloque GetKey que monitoriza cual de los botones del NXT es pulsado y da como resultado un número que se puede usar para hacer que se ejecute una determinada acción.

Como el programa de Brian Davis depende enteramente del teclado – y llegué a encontrarlo algo engorroso para meter el número inicial – decidí usar un motor como método de entrada, en combinación con los botones para añadir dígitos (de más a menos, es decir si tengo un 1 y añado un 9 el resultado es 19), restarlos (dar un paso atrás y volverá  quitar ese 9, dejando solo 1) o aceptar el valor para el cálculo.

El cálculo se puede hacer de dos maneras: automático y paso a paso. El modo paso a paso permite ver cada iteración del cálculo y muestra el resultado hasta ese momento y el número de pasos ejecutados.

Este puede ser un buen momento para dar un ejemplo de esos pasos. Supongamos que empecemos por un numero bajo: 5. La secuencia que se desarrolla es la siguiente

5 – 16 – 8 -4 – 2 – 1  un total de 5 iteraciones

Para 7 la secuencia es:

7 – 22 – 11  - 34 – 17 – 52 – 26 – 13 – 40 – 20 – 10 – 5 – 16 – 8 – 4 – 2 – 1 un total de 16 iteraciones, parte de las cuales coinciden con las de 5

En el NXT queda de la siguiente manera: después de seleccionar el número se puede elegir hacer proceso paso a paso (botón derecho), automático (botón izquierdo), o salir (botón central)

Haciéndolo de manera manual se pueden ver los pasos intermedios y en cualquier caso el resultado final:

Algunas ideas de programación:

Como se puede ver en la fórmula que aparece más arriba, una manera de saber si un número es par o impar es calcular el módulo de la división entre 2. Yo tampoco soy de mates, pero en programación el módulo es la parte del número que no se puede dividir si usar fracciones: así el módulo de 4/3 es 1.

Aquí nos podemos aprovechar del hecho de que NXT-G 1 solo funciona con números enteros... no sabe de decimales. NXT-G 2.0 sí usa coma flotante por lo que en un principio no se podría hacer lo mismo, pero... es posible instalar de manera sencilla los 'antiguos' bloques' de números enteros en NXT-G 2.0!

Usando estos bloques se puede obtener el módulo de la siguiente manera:

Primero divido un número entre 2 (en la fórmula más arriba hablábamos del módulo de 2) y el resultado se multiplica por 2. Si el número fue par la división es "limpia" y el resultado de la multiplicación será el mismo. La diferencia entre el número original y el resultado de la multiplicación será 0.
Si el número es impar, la división generará un resto que se pierda al no poder procesarlo el bloque de matemáticas 'integras' y la comparación arrojará un saldo positivo. De este modo se sabe si hay que aplicar  n/2 o 3n+1 al número.

¿Cómo instalar esos bloques? Es muy sencillo, pero no lo voy a poner aquí  X)
He empezado a hacer una compilación de bloques adicionales para NXT-G en la wiki de LRoboticas. En el apartado "Datos" hay una entrada para los "Bloques con números enteros"
donde explico cómo hacer precisamente esto.

[manticore]

Me ha recordado cuando hacía mis pinitos con la programación de mi hp48GX, tanto en User-RPL como en Sys-RPL (los dos lenguajes más extendidos en el mundillo "jacapaca"). Y muy curiosa la conjetura del Sr. Collatz, no la conocía (en este foro se aprende de todo, diga lo que diga el ministro Gabilondo :D :D :D).
A ver si los chicos MINDSTORMS se atreven con el último teorema de Fermat que se demostró hace bien poco ;)

[Blastem]

Mmm Cálculo Numérico  :_(  :_(  :_(

Una bonita hipótesis Matemática traducida a Mindstorms.
Una buena forma de practicar con los comandos while e if (O su equivalente LEGO  :angel:)

[Jetro]

Efectivamente Blastem, if y más if ya que NXT-G no tiene While (el while se consigue juntando un if con un bucle).

Me he dado cuenta de que me he quedado algo corto en mi primer mensaje ya que faltan algunas cosillas. Una foto de "MOC" por ejemplo; así que para saldar la deuda:



Tampoco he enseñado ninguno de los bloques creados por Brian Davis que he aprovechado para el programa.  Se trata de los siguientes:


PrintNumber Permite escribir un número precedido de una leyenda o "etiqueta". De esta manera se combinan dos funciones que de otra manera habría que implementar por separado. Aprovecha la posibilidad que brinda el bloque de texto de concatenar varios fragmentos: en este caso unir una leyenda y un número previamente convertido en 'texto'.



PrintLine Para que el anterior bloque funcione hace falta este otro bloque especial. No hace más que calcular la posición en píxeles de la línea deseada (cada línea tiene una altura de 8 píxeles y la línea 8 empieza en 0 píxeles) para leugo permitir insertar texto en esa línea.



Printscreen También hace uso del bloque PrintLine. Parece una tontería pero es un bloque de lo más práctico. Permite - a través del panel de configuración del bloque - escribir en una vez todo el texto que se quiere mostrar en la pantalla, en vez de tener que hacerlo línea por línea.




Manti: después de leer un poco sobre Fermat en Inet sigo igual... no veo por donde cogerlo para transformarlo en algo que se pueda hacer con un NXT, más que nada porque consistiría en demostrar que algo NO es posible: justo lo contrario de la conjetura Collatz que dice que SI es posible. Pero si tienes alguna sugerencia sobre cómo hacerlo...

[manticore]

Es cierto, este famoso teorema afirma que no existen números naturales que cumplan x^n + y^n = z^n. Se trata de una desigualdad, no de una igualdad.

Pero si tienes alguna sugerencia sobre cómo hacerlo...

Sabes que mis competencias abarcan naves gigantes y montañas inmensas... ¡¡no estoy preparado!! :_( :_(

[Blastem]

LEGO-Demostración

Bricks^n + Slopes^n=(Dimensiones Mantianas)^n   :D  :D  :angel:

Es un Teorema feo de programar para buscar soluciones, ya que tienen que ser aproximadas numéricamente (Ya que con enteros hay más bien pocas que no sean múltiplos)

[31415926]

Me ha gustado mucho el sistema de entrada, seguro que lo usaré  :). El problema es ideal para enseñar sentencias de flujo y además das utilidad a muchos bloques para NXT-G. Tendrías que poner la traducción para NXC o RobotC para que se vea como se simplifica el programa  ;).

Esto si que si :B, enunciados pequeños problemas gigantes:
Cuadratura del círculo -> dos milenios: Teoría de grupos.
Teorema de Fermat -> 350 años: Teoría algebraica, teorema de moludaridad. Tendrían que hacer los libros con más margen.
Conjetura de Collatz ->  ??? ¿Qué nos deparará? ¿Lo viviremos?
...
Muchos otros que se quedan en el tintero.

[Jetro]

Para completar la primera fase del proyecto aún os debía el código en NXT-G

En cuento esté disponible se podrá descargar aquí: http://www.megaupload.com/?d=CX0HVXKA

He tardado un poco porque aunque el código funcionaba me estaba dando algunos problemas - no siempre compilaba bien dependiendo de si usaba NXT-G Retail o Edu y tardaba mucho en abrirse en cualquiera de los dos. He podido localizar los problemas - guardaban relación con el hecho que sacar hilos de un bloque de conmutación (if) no parece buena praxis...

Más adelante quiero ver si puedo rescribir el código para NXC, salvo que alguien se me adelante  :D

[Jetro]

Después de analizar el comportamiento de las series generadas por algunos números vi necesario añadir otra lectura al proyecto inicial: la del número máxima alcanzado.

Calculando los números del 1 al 30 sobresale el 27: tiene un tiempo de órbita (número de iteraciones necesarias para llegar a 1) de 111 (¡) y el valor máximo que alcanza es de 9232. ¿Será que las series tienen números preferidos? Hasta el 27 todo estaba más o menos controlado. ¿Será una excepción? ¿Habrá un tiempo de órbita medio para cada rango de valores?

Para poder dar respuesta a esas preguntas hará falta otro programa que recoja datos a mayor velocidad porque mirando de uno en uno ...

Dicho y hecho, el nuevo programa (se llama Collatz a secas y se puede descargar aquí: http://www.megaupload.com/?d=69810RF8).

El programa ha pasado por bastantes cambios a medida que iba consiguiendo resultados, aunque el principio sigue siendo el mismo: además de aplicar la comprobación de par/impar y la operación matemática correspondiente según el caso, el programa guarda datos en un archivo de texto en el NXT. El 'problema' de esta técnica es que NXT-G usa una nueva línea para cada dato. Sin embargo hay un sencillo truco para poder guardar datos correlacionados (número, tiempo de órbita y máximo): convertir los números en texto (el aspecto sigue siendo el mismo pero el programa lo trata de manera diferente) y concatenar esos datos, insertando comas. El archivo resultante tiene este aspecto:

1,0,1
2,1,2
3,7,16
4,2,4
5,5,16
6,8,16
7,16,52
8,3,8
9,19,52
10,6,16
Etc. etc.

Inicialmente hice un bucle con contador para calcular los primeros 1000 números, pero al ver la velocidad con la que se calculaban las series decidí hacer un bucle infinito... y parar cuando me cansara.

Dejé correr el contador hasta 10.000, pero curiosamente el archivo que obtuve se paraba bruscamente (sin siguiera terminar de escribir uno de los números) poco después de los 1.000.

Al revisar la memoria del NXT me di cuenta de que tenía unos cuantos programas en el NXT y que por eso seguramente se había truncado la creación del archivo.  Borré absolutamente todo lo que se puede borrar (incluido archivos 'de sistema' al que tienes acceso desde NXT-G) y probé nuevamente:

Esta vez el resultado fue bastante mejor, pero aún así el archivo se truncaba alrededor de los 4.000. Por si acaso desfragmenté la memoria del NXT (esto se puede hacer con una opción en el programa NeXTExplorer) y repetí la prueba... con idéntico resultado.

A continuación descubrí que la misma herramienta con la que puedes borra o descargar archivos del NXT (la segunda pestaña de la ventana de enlace con el NXT) permite ver en tiempo real algo de lo que pasa con la memoria del NXT. Así descubrí que cada pocos segundos se creaba un archivo con el mismo nombre que el que usaba para recoger los datos, pero terminado en .bak. Por alguna razón, de vez en cuando se crea un archivo de respaldo que posteriormente vuelve a desaparecer, pero para hacer esto en NXT necesita tener el doble de espacio libre que el tamaño del archivo final, por lo que la función se trunca al consumir la mitad del espacio disponible :(

Cabía una última optimización: obviar el número calculado de la serie: más adelante, al importar los datos en una hoja de cálculo, el número de fila puede asumir esa función así que el dato sobra. De este modo se puede recoger los datos de casi un tercio más de números con lo que he llegado a los 6.000

¿ Las conclusiones?
Para empezar el tiempo de órbita. Aunque los tiempos de órbita de números cercanos se pueden parecer también hay grandes variaciones y no hay ningún patrón evidente. Sin embargo llama la atención que ciertos valores tienen tiempos idénticos, estando uno  al lado del otro. 12 y 13 o 20 y 21 o 52 y 53 tienen tiempos de órbita idénticos. Sin embargo 14 casi duplica el tiempo de órbita de 12 y 13...

En cuanto a los valores máximos, las cosas son similares aunque un poco más estructuradas. Eliminando los valores más altos se puede observar claramente una línea de 'preferencia' en la altura de 9232 y varias líneas de números que se acoplan a múltiplos de su valor inicial (1, 1.5, 3, 4,5, 6,75...)


En la segunda imagen he ajustado el eje vertical con una escala logarítmica para poder ver todos los valores generados.



Es curioso ver cómo, aparte de la evidente línea de 9232, hay más líneas horizontales de 'preferencia' visibles.

Si alguien quiere ver el archivo de datos generado con el NXT, lo adjunto al mensaje.

[31415926]

Al no ser que me contradigas, no tendría que adelantarse nadie: has investigado, subido imágenes, confeccionado el hilo, programa NXT-G, ...

Otra cosa es que no quieras/puedas dedicarle más tiempo.

Edit: No es el caso, no había visto tu último mensaje, buenisimo. :)

[chasplas]

si en vez de matlab, se utilizara en NXT en las clases de matematicas, aprobaria mas gente, seguro  :angel:

[Blastem]

A esto le llamo yo "quedarse contento"  :D

Te has marcado un análisis numérico con NXT llevando la capacidad de proceso hasta su límite y analizando los datos obtenidos. (Intersesante lo de la creación de un bak para los procesos  B))

Excelente lo que has hecho  :angel:

[manticore]

De verdad que este ladrillín nunca deja de sorprendernos B)

[JOYBRICK]

lo siento,por algo no me gusta lo technic,no entendi naaadaaa! :_(

[Jetro]

Es que no es Technic, es MINDSTORMS. Curiosamente en este caso los ladrillos apenas tienen algo que ver con todo el tema y aún así es LEGO  :angel:

Para hacerlo todo un poco más fácil de digerir he pensado hacer un poster. Creo que una de las cosas que faltaron en la sección Technic/MINDSTORMS de la pasada Hispabrick fueron más medios (audio)visuales (aunque hubiera sido difícil poderlos colgar en alguna parte) así que pensando ya en el futuro he hecho un poster (tamaño A3) que podría servir de apoyo para explicar el proyecto. Posiblemente aún haya que limar algunos aspectos, pero creo que es una opción muy interesante

(Si pinchas en la imagen se abre en la galería del foro.
Si vuelves a pinchar se abre a tamaño mayor)