Menu Close

Categoría: Haskell

Problema de Ramanujan de radicales anidados

El viernes pasado, John D. Cook escribió el artículo Ramanujan’s nested radical en el que comenta el siguiente problema planteado por Ramanujan en el Journal of Indian Mathematical Society:

¿Cuál es el valor de la siguiente expresión?
\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\ldots}}}}

A partir del problema he elaborado la siguiente relación de ejercicios en Haskell para la asignatura de Informática (de 1º del Grado en Matemáticas).

El problema de las sucesiones llenas en Haskell

En las Olimpiadas de Matemáticas del 2002 se propuso el siguiente problema

Sea n un entero positivo. Una sucesión de n enteros positivos (no necesariamente distintos) se llama “llena” si verifica la siguiente condición: para cada entero positivo k ≥ 2, si el número k aparece en la sucesión, entonces también lo hace el número k-1 y, además, la primera ocurrencia de k-1 es anterior a la última ocurrencia de k. Para cada n, ¿cuántas sucesiones llenas existen?

En la siguiente relación de ejercicios, elaborada para la asignatura de Informática (de 1º del Grado en Matemáticas), se estudia con Haskell el problema.

Los números de Ulam en Haskell

Los números de Ulam son los elementos de la sucesión u(n) definida por u(1) = 1, u(2) = 2 y, para n > 2, u(n) es el entero más pequeño que se puede escribir exactamente de una forma como suma de dos términos anteriores diferentes entre sí.

Según la definición, 3=1+2 es un número de Ulam y 4=1+3 también es un número de Ulam (la suma 4=2+2 no cuenta porque los términos previos deben ser distintos). El entero 5 no es un número de Ulam porque 5=1+4=2+3.

Los primeros términos de la sucUlam son: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99.

Esta sucesión fue definida por el matemático polaco Stanislaw Ulam y
publicada en SIAM Review en 1964.

A partir de los artículos de la Wikipedia y de MathWorld sobre los números de Ulam elaborado la siguiente relación de ejercicios de Haskell para la asignatura de Informática de 1º del Grado en Matemáticas.

En la relación se presentan cuatro definiciones de los números de Ulam, se compara su eficiencia, se muestra algunas de sus propiedades terminando con los números de Ulam generalizados.

PeH: Piensa en Haskell (Ejercicios de programación funcional con Haskell)

He publicado la primera versión de libro Piensa en Haskell (Ejercicios de programación funcional con Haskell).

Este libros es una introducción a la programación funcional con Haskell a través de una colección de ejercicios resueltos de los cursos de Informática (del
Grado en Matemáticas) y Programación declarativa (de la Ingeniería en Informática).

Los temas correspondientes a los ejercicios del libro se encuentra en Temas de programación funcional.

El libro consta de tres partes. En la primera parte se presentan los elementos básicos de la programación funcional. En la segunda, se estudian la implementación en Haskell de tipos abstractos de datos y sus aplicaciones así como cuestiones algorítmicas. En la tercera, se presentan casos de estudios. También se han incluido dos apéndices: uno con un resumen de las funciones de Haskell utilizadas y otro con el método de Pólya para la resolución de problemas.

Biparticiones con igual suma que producto en Haskell

En Números y algo más … se ha planteado el siguiente problema

¿Es posible dividir todos los números del 1 al 2012 en dos grupos, S y P, tal que la suma de los números de S sea igual al producto de los números que están en P? ¿y si fueran 2011 ó 2013? Si es posible, ¿Cómo estarían formados esos conjuntos?

En la siguiente relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas) se resuelve el problema con Haskell.

El algoritmo de Moessner en Haskell

La presente relación de ejercicios está basada en el artículo El algoritmo de Moessner escrito por Antonio Roldán Martínez en su blog Números y hoja de cálculo.

El proceso de Moessner de orden n consiste en lo siguiente: De la lista de los números naturales, se tacha los elementos que ocupan las posiciones n, 2*n, … y se forma la sucesión de las sumas parciales de los restantes elementos. De la resultante sucesión se tacha los elementos que ocupan las posiciones n-1, 2*(n-1), … y se forma la sucesión de las sumas parciales de los restantes elementos. El proceso se repite n-1 veces. Por ejemplo, para n=2:

1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 ...  [Inicial]
1   3   5    7     9    11    13    15    ...  [Elimina 2]
1   4   9   16    25    36    49    64    ...  [Sumas acumuladas]

Se observa que los elementos de la última es la sucesión de los cuadrados. Para n=3, el proceso de Moessner es

1 2 3 4  5 6  7  8  9 10 11 12 13 14 15 16 ... [Inicial]
1 2   4  5    7  8    10 11    13 14    16 ... [Elimina 3]
1 3   7 12   19 27    37 48    61 75    91 ... [Sumas acumuladas]
1     7      19       37       61       91 ... [Elimina 2]
1     8      27       64      125      216 ... [Sumas acumuladas]

Se observa que los elementos de la última es la sucesión de los cubos. Para n=4, el proceso de Moessner es

1 2 3 4  5  6  7  8  9  10 11 12 13  14 15 16 ... [Inicial]
1 2 3    5  6  7     9  10 11    13  14 15    ... [Elimina 4]
1 3 6   11 17 24    33  43 54    67  81 96    ... [Sumas acumuladas]
1 3     11 17       33  43       67  81       ... [Elimina 3]
1 4     15 32       65 108      175 256       ... [Sumas acumuladas]
1       15          65          175           ... [Elimina 2]
1       16          81          256           ... [Sumas acumuladas]

Se observa que los elementos de la última es la sucesión de los cuartas potencias. El teorema de Moessner afirma que para cualquier n, la sucesión obtenida mediante el proceso de Moessner es la de las potencias n-ésimas; es decir 1^n, 2^n, 3^n, 4^n, \dots

El objetivo de los siguientes ejercicios es definir en Haskell una función que simule el proceso de Moessner y comprobar el teorema.

I1M2011: Libro de ejercicios resueltos de programación en Haskell (v. 30-May-12)

A lo largo del curso iré actualizando un libro de ejercicios resueltos de programación con Haskell con las relaciones de ejercicios del curso de Informática (de 1º del Grado en Matemáticas)

En la versión actual contiene las soluciones de las 33 primeras relaciones y los 6 primeros exámenes:

  1. Definiciones elementales de funciones (1).
  2. Definiciones elementales de funciones (2).
  3. Definiciones por comprensión (1).
  4. Definiciones por comprensión (2).
  5. Definiciones por comprensión (3): El cifrado César.
  6. Definiciones por recursión.
  7. Definiciones por recursión y por comprensión (1).
  8. Definiciones por recursión y por comprensión (2).
  9. Definiciones sobre cadenas, orden superior y plegado.
  10. Definiciones por plegado.
  11. Codificación y transmisión de mensajes.
  12. Resolución de problemas matemáticos.
  13. Demostración de propiedades por inducción.
  14. El 2011 y los números primos.
  15. Listas infinitas.
  16. Ejercicios de exámenes del curso 2010-11.
  17. Combinatoria.
  18. Tipos de datos algebraicos.
  19. Tipos de datos algebraicos: árboles binarios.
  20. Tipos de datos algebraicos: fórmulas proposicionales.
  21. Tipos de datos algebraicos: Modelización de juego de cartas.
  22. Cálculo numérico.
  23. Ecuación con factoriales.
  24. Aplicaciones de la programación funcional con listas infinitas.
  25. División y factorización de polinomios mediante la regla de Ruffini.
  26. Operaciones con el TAD de polinomios.
  27. Operaciones con vectores y matrices.
  28. Ejercicios complementarios.
  29. Relaciones binarias.
  30. Operaciones con conjuntos.
  31. Implementación del TAD de los grafos mediante listas.
  32. Problemas básicos con el TAD de los grafos.
  33. Enumeraciones de los números racionales.
  34. Exámenes:
    • Examen 1 (26 de Octubre de 2011).
    • Examen 2 (30 de Noviembre de 2011).
    • Examen 3 (25 de Enero de 2012).
    • Examen 4 (29 de Febrero de 2012).
    • Examen 5 (21 de Marzo de 2012).
    • Examen 6 (2 de Mayo de 2012).

Cuadrados con los dígitos duplicados en Haskell

La semana pasada se planteó en “Números y algo más …” el problema de los cuadrados con los dígitos duplicados cuyo enunciado es el siguiente:

Si elevamos 72576, que tiene un 2, un 5, un 6 y dos 7, al cuadrado obtenemos 5267275776 el cual tiene exactamente dos 2, dos 5, dos 6 y cuatro 7. Es decir que si en el número original el dígito d aparece v veces, en el cuadrado, d aparece 2v veces. ¿Cual es el siguiente número con esta propiedad? ¿Habrá algún primo que lo haga?

En la siguiente relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas) se resuelve el problema con Haskell.

Límites de sucesiones y tipos de números en Haskell

En Haskell se dispone de tres tipos para trabajar con los números racionales: dos como números aproximados (Float y Double) y uno como números exactos (Rational). En este ejemplo veremos cómo el uso de números aproximados puede conducir a falsas conjeturas sobre límites de sucesiones que pueden refutarse con el uso de los números exactos. Para ello consideraremos tres definiciones de la sucesión u:

\begin{array}{l}     u_0 = \frac{3}{2} \\ \\     u_1 = \frac{5}{3} \\ \\     u_{n} = 2003 - \frac{6002}{u_{n-1}} + \frac{4000}{u_{n-1} \cdot u_{n-2}},         \mbox{ para } n \geq 2     \end{array}

usando en cada caso uno de los tipos y conjeturando el límite de la sucesión.