Menu Close

Etiqueta: PeH

El triángulo de Floyd en Haskell

El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son

 1
 2   3
 4   5   6
 7   8   9  10
11  12  13  14  15

El triángulo de Floyd tiene varias propiedades matemáticas interesantes:

  • los números de la hipotenusa es la sucesión de los números triangulares; es decir, los números que puede ser representado como puntos dispuestos en forma de triángulo, empezando por el 1. Los primeros números triangulares son

    triangulares
  • los números del cateto de la parte izquierda es la sucesión de los números poligonales centrales; donde el n-ésimo número poligonal centrado es el máximo número de piezas que se pueden obtener a partir de un círculo con n líneas rectas. Los primeros números poligonales centrados son

    poligonales_centrados

En la siguiente relación de ejercicios (elaborada para I1M) se define en Haskell el triágulo de Floyd y se comprueban algunas de sus propiedades.

Números poligonales y sus propiedades en Haskell

Un número poligonal es aquel que puede ser representado como puntos dispuestos en forma de polígono regular, empezando por el 1. Los primeros números poligonales son los números triangulares, estos se forman a partir de triángulos.
triangulares
Los siguientes son los números cuadrangulares
cuadrados
Los siguientes son los números pentagonales
pentagonales

Los números triangulares son 1, 3, 6, 10, 15, 21, … Sus diferencias son 2, 3, 4, 5, 6, … Por tanto, se obtienen como sigue

1 = 1
3 = 1+2
6 = 1+2+3
10 = 1+2+3+4
15 = 1+2+3+4+5
21 = 1+2+3+4+5+6

Los números cuadrangulares son 1, 4, 9, 16, 25, 36, 49, … Sus diferencias son 3, 5, 7, 9, … Por tanto, se obtienen como sigue

1 = 1
4 = 1+3
9 = 1+3+5
16 = 1+3+5+7
25 = 1+3+5+7+9
36 = 1+3+5+7+9+11
49 = 1+3+5+7+9+11+13

Los números pentagonales son 1, 5, 12, 22, 35, … Sus diferencias son 4, 7, 10, 13, … Por tanto, se obtienen como sigue

1 = 1
5 = 1+4
12 = 1+4+7
22 = 1+4+7+10
35 = 1+4+7+10+13

Siguiendo el mismo patrón, las diferencias entre los números hexagonales son 5, 9, 13, 17, … Por tanto, los primeros números hexagonales son

1 = 1
6 = 1+5
15 = 1+5+9
28 = 1+5+9+13
45 = 1+5+9+13+17

Continuando con este patrón se obtienen los número poligonales con k lados. Los siguientes son

k=7 Heptagonal: 1, 7, 18, 34, 55, 81, 112, 148, 189, 235, …
k=8 Octagonal: 1, 8, 21, 40, 65, 96, 133, 176, 225, 280, …
k=9 Nonagonal: 1, 9, 24, 46, 75, 111, 154, 204, 261, 325, …

En la siguiente relación de ejercicios (elaborada para I1M) se muestran distintas definiciones de los números poligonales y algunas de sus propiedades, como el teorema de Fermat, en Haskell.

El juego de Oslo en Haskell

En el número especial de la revista Mundo científico sobre El universo de los números se presenta el juego de Oslo. En dicho juego
se trata de obtener cualquier número natural no nulo, por medio de aplicaciones sucesivas de una de las reglas siguientes:

  1. poner un cero al final del número,
  2. poner un cuatro al final del número y
  3. dividir por 2 si el número es par.

Por ejemplo, el 3 y el 5 se pueden obtener como sigue

   4 -> 2 -> 24 -> 12 -> 6 -> 3
   4 -> 2 ->  1 -> 10 -> 5

En la siguiente relación de ejercicios (elaborada para I1M) veremos qué números se pueden alcanzar, cómo y en cuántos pasos. Además, se presentan distintas soluciones comparando sus eficiencias.

PeH: Codificación por longitud en Haskell

La codificación por longitud, o comprensión RLE (del inglés, “Run-length encoding”), es una compresión de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento. Por ejemplo, la cadena

BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB

se codifica por

12B1N12B3N24B1N14B

Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras N, etc.

En los siguientes ejercicios se definirán funciones para codificar y descodificar por longitud y comprobar que son operaciones inversas.

PeH: Sucesión de Fibonacci, evaluación perezosa y números construibles

Continuando con ejemplos de evaluación perezosa en Haskell, un clásico es la sucsión de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … cuyos dos primeros términos son 0 y 1 y los restantes se calcula sumando los dos anteriores.

En la siguiente relación de ejercicios se presentan distintas definiciones de la sucesión de Fibonacci basadas en la evaluación perezosa y la última
usando números construibles mediante la librería Data.Real.Constructible.

PeH: El triángulo de Pascal en Haskell

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

construido de la siguiente forma

  • la primera fila está formada por el número 1;
  • las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La construcción del triángulo de Pascal sirve para ilustrar cómo se puede trabajar con listas infinitas en Haskell usando la evaluación perezosa como se muestra en los siguientes ejercicios.

PeH: La conjetura de Gilbreath en Haskell

Se considera el siguiente proceso: (1) escribir los 5 primeros números primos, (2) restar cada dos números consecutivos, escribiendo los resultados en valor absoluto, hasta quedarse con un único número se obtiene la siguiente tabla:

2, 3, 5, 7, 11
1, 2, 2, 4 
1, 0, 2
1, 2 
1

Se observa que todas las filas comienza con el número 1.

Repitiendo el proceso empezando con los 8 primeros números primos se obtiene la siguiente tabla:

2, 3, 5, 7, 11, 13, 17, 19 
1, 2, 2, 4,  2,  4,  2  
1, 0, 2, 2,  2,  2 
1, 2, 0, 0,  0 
1, 2, 0, 0 
1, 2, 0 
1, 2 
1

Se observa que, de nuevo, todas las filas comienza con el número 1.

La conjetura de Gilbreath afirma que si escribimos la sucesión de números primos completa y después construimos las correspondientes sucesiones formadas por el valor absoluto de la resta de cada pareja de números consecutivos, entonces todas esas filas que obtenemos comienzan siempre por 1.

En los siguiente ejercicios comprobaremos experimentalmente con Haskell dicha conjetura. Para la representación, usaremos la simétrica de la que
hemos comentado anteriormente; es decir,

 2
 3, 1
 5, 2, 1
 7, 2, 0, 1
11, 4, 2, 2, 1
13, 2, 2, 0, 2, 1
17, 4, 2, 0, 0, 2, 1
19, 2, 2, 0, 0, 0, 2, 1

en la que la primera columna son los números primos y el elemento de la fila i y columna j (con i, j > 1) es el valor absoluto de la diferencia de los elementos (i,j-1) e (i-1,j-1).

La relación de ejercicios (elaboradad para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) es

PeH: La sucesión de Kolakoski

Dada una sucesión, su contadora es la sucesión de las longitudes de de sus bloque de elementos consecutivos iguales. Por ejemplo, la sucesión contadora de abbaaabbba es 12331; es decir; 1 vez la a, 2 la b, 3 la a, 3 la b y 1 la a.

La sucesión de Kolakoski es una sucesión infinita de los símbolos 1 y 2 que es su propia contadora. Los primeros términos de la sucesión de Kolakoski son 1221121221221… que coincide con su contadora (es decir, 1 vez el 1, 2 veces el 2, 2 veces el 1, …).

En la siguiente relación (para la asignatura de Informática de 1º del Grado en Matemáticas y para la siguiente versión del libro Piensa en Haskell) se define la sucesión de Kolakoski.