Description

Pr´actica 5 La conjetura de Collatz
Nota Importante:

Cuando se solicite la entrega de esta pra´ctica, cada alumno debera´ subir a su repositorio de pra´cticas (del cual se indicara´ su ubicaci´on ma´s adelante) un directorio p5 cuyo contenido debe ser u´nicamente el fichero collatz.ml.
Sea muy cuidadoso a la hora de crear el directorio y los ficheros, y respete los nombres indicados. En particular, f´ıjese que todos estos nombres so´lo contienen letras en minu´sculas, nu´meros y puntos.
Adema´s, todos los ficheros deben compilar sin errores con las siguientes o´rdenes: ocamlc -c collatz.ml
Ejercicios:

1. Considere la funcio´n f de N→N, que podr´ıa aproximarse en OCaml con la siguiente definicio´n para f: int -> int
let f n = if n mod 2 = 0 then n / 2 else 3 * n + 1
Segu´n la Conjetura de Collatz , si partimos de cualquier nu´mero positivo y vamos aplicando repetidamente esta funcio´n, seguiremos un camino que llegara´ inexorablemente al 1. Por ejemplo, partiendo del 13, tendr´ıamos el siguiente camino:
13,40,20,10,5,16,8,4,2,1
Llamaremos “´orbita” de un nu´mero al camino que se sigue de esta manera desde ese nu´mero hasta el 1 (ambos incluidos). Por ejemplo, la que hemos escrito ma´s arriba es la o´rbita del 13.
En un archivo con nombre collatz.ml, defina (de modo recursivo) en OCaml una “funcio´n” orbit: int -> unit tal que, cuando se aplique esta funci´on a cualquier n > 0 se env´ıe a la salida esta´ndar una l´ınea con la ´orbita de n, siguiendo el formato del ejemplo (los distintos valores por los que pasa la o´rbita deben estar separados por una coma y un espacio y debe terminarse con un salto de l´ınea).
# orbit;;
– : int -> unit = <fun>
# orbit 13;;
13, 40, 20, 10, 5, 16, 8, 4, 2, 1
– : unit = ()
# orbit 1;;
1
– : unit = ()
An˜ada al mismo archivo la definicio´n (recursiva) de una funcio´n length: int -> int, tal que, para cualquier n > 0, length n sea el nu´mero de pasos necesarios (en la o´rbita de n) para llegar hasta el 1. As´ı, por ejemplo, length 13 debe ser 9.
# length;;
– : int -> int = <fun>
# length 13;;
– : int = 9
# length 27;;
– : int = 111
An˜ada al mismo archivo la definici´on (recursiva) de una funci´on top: int -> int, tal que, para cada n > 0, top n sea el valor ma´s alto alcanzado en la o´rbita de n. As´ı, por ejemplo, top 13 debe ser 40.
# top;;
– : int -> int = <fun>
# top 13;;
– : int = 40
# top 27;;
– : int = 9232
Defina tambi´en directamente (de modo recursivo, sin usar las funciones length y top) una funcio´n length’n’top: int -> int * int, tal que, para cada entero n, devuelva un par de enteros indicando la longitud de su o´rbita y su altura ma´xima. As´ı, por ejemplo, length’n’top 13 deber´ıa ser el par (9, 40). Se trata de que al aplicar esta definicio´n “no se recorra dos veces la ´orbita en cuestio´n”. (An˜ada esta definici´on al archivo collatz.ml).
# length’n’top;;
– : int -> int * int = <fun>
# length’n’top 13;;
– : int * int = (9, 40)
# length’n’top 27;;
– : int * int = (111, 9232)
2. Ejercicio opcional. Defina una funci´on longest in: int -> int -> int tal que longest in m n devuelva el menor valor del intervalo [m,n] cuya ´orbita tenga longitud maximal en ese intervalo. As´ı, por ejemplo, longest in 86 87 deber´ıa ser 86. (An˜ada esta definici´on al archivo collatz.ml).
Defina una funci´on highest in: int -> int -> int tal que highest in m n devuelva el menor valor del intervalo [m,n] cuya ´orbita tenga altura maximal en ese intervalo. As´ı, por ejemplo, highest in 86 87 deber´ıa ser 87. (An˜ada esta definici´on al archivo collatz.ml).
# longest_in;;
– : int -> int -> int = <fun>
# highest_in;;
– : int -> int -> int = <fun>
# longest_in 1 1000;; – : int = 871
# highest_in 1 1000;;
– : int = 703