Número de sumandos en suma de cuadrados

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

Definir las funciones

tales que

  • (ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.

  • (graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Soluciones

Pensamiento

— Nuestro español bosteza.
¿Es hambre? ¿Sueño? ¿Hastío?
Doctor, ¿tendrá el estómago vacío?
— El vacío es más bien en la cabeza.

Antonio Machado

Simplificación de expresiones booleanas

El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

y (simplifica p) es una expresión obtenida aplicándole a p las siguientes reglas de simplificación:

Por ejemplo,

Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Para la comprobación, de define el generador

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

Soluciones

Pensamiento

¿Dices que nada se pierde?
Si esta copa de cristal
se me rompe, nunca en ella
beberé, nunca jamás.

Antonio Machado

Árboles con n elementos

Los árboles binarios se pueden representar con

Definir las funciones

tales que

  • (arboles n x) es la lista de todos los árboles binarios con n elementos iguales a x. Por ejemplo,

  • nArboles es la sucesión de los números de árboles con k elementos iguales a 7, con k ∈ {1,3,5,…}. Por ejemplo,

Soluciones

Pensamiento

Ni vale nada el fruto
cogido sin sazón …
Ni aunque te elogie un bruto
ha de tener razón.

Antonio Machado

Recorrido de árboles en espiral

Los árboles se pueden representar mediante el siguiente tipo de datos

Por ejemplo, los árboles

se representan por

Definir la función

tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,

Soluciones

Pensamiento

Dice la monotonía
del agua clara al caer:
un día es como otro día;
hoy es lo mismo que ayer.

Antonio Machado

Posiciones del 2019 en el número pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Definir la función

tal que (posicion cs k) es es la lista de las posiciones iniciales de cs en la sucesión formada por los k primeros dígitos decimales del número pi. Por ejemplo,

Calcular la primera posición de 2019 en los decimales de pi y el número de veces que aparece 2019 en en el primer millón de decimales de pi.

Soluciones

Pensamiento

Aprendió tantas cosas, que no tuvo tiempo para pensar en ninguna de ellas.

Antonio Machado

Representación de conjuntos mediante intervalos

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

tal que (intervalos xs) es lista ordenada de intervalos que representa
al conjunto xs. Por ejemplo,

Soluciones

Pensamiento

Cuando el saber se especializa, crece el volumen total de la cultura. Esta es la ilusión y el consuelo de los especialistas. ¡Lo que sabemos entre todos! ¡Oh, eso es lo que no sabe nadie!

Antonio Machado

Cadena descendiente de subnúmeros

Una particularidad del 2019 es que se puede escribir como una cadena de dos subnúmeros consecutivos (el 20 y el 19).

Definir la función

tal que (cadena n) es la cadena de subnúmeros consecutivos de n cuya unión es n; es decir, es la lista de números [x,x-1,…x-k] tal que su concatenación es n. Por ejemplo,

Nota: Los subnúmeros no pueden empezar por cero. Por ejemplo, [10,09] no es una cadena de 1009 como se observa en el tercer ejemplo.

Soluciones

Pensamiento

La inseguridad, la incertidumbre, la desconfianza, son acaso nuestras únicas verdades. Hay que aferrarse a ellas.

Antonio Machado

El 2019 es un número de la suerte

Un número de la suerte es un número natural que se genera por una criba, similar a la criba de Eratóstenes, como se indica a continuación:

Se comienza con la lista de los números enteros a partir de 1:

Se eliminan los números de dos en dos

Como el segundo número que ha quedado es 3, se eliminan los números restantes de tres en tres:

Como el tercer número que ha quedado es 7, se eliminan los números restantes de siete en siete:

Este procedimiento se repite indefinidamente y los supervivientes son los números de la suerte:

Definir las funciones

tales que

  • numerosDeLaSuerte es la sucesión de los números de la suerte. Por ejemplo,

  • (esNumeroDeLaSuerte n) que se verifica si n es un número de la suerte. Por ejemplo,

Soluciones

Pensamiento

Ya es sólo brocal el pozo;
púlpito será mañana;
pasado mañana, trono.

Antonio Machado

Menor contenedor de primos

El n-ésimo menor contenenedor de primos es el menor número que contiene como subcadenas los primeros n primos. Por ejemplo, el 6º menor contenedor de primos es 113257 ya que es el menor que contiene como subcadenas los 6 primeros primos (2, 3, 5, 7, 11 y 13).

Definir la función

tal que (menorContenedor n) es el n-ésimo menor contenenedor de primos. Por ejemplo,

Soluciones

Pensamiento

¡Ya hay hombres activos!
Soñaba la charca
con sus mosquitos.

Antonio Machado

Raíz cúbica entera

Un número x es un cubo si existe un y tal que x = y^3. Por ejemplo, 8 es un cubo porque 8 = 2^3.

Definir la función

tal que (raizCubicaEntera x n) es justo la raíz cúbica del número natural x, si x es un cubo y Nothing en caso contrario. Por ejemplo,

Soluciones

Pensamiento

Tras el vivir y el soñar,
está lo que más importa:
despertar.

Antonio Machado

Sucesión fractal

La sucesión fractal

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales

  • los términos impares forman la misma sucesión original

Definir las funciones

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

Soluciones

[schedule expon=’2018-06-19′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 17 de mayo.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2018-06-19′ at=»06:00″]

Referencia

+ [Fractal sequences and restricted Nim](http://bit.ly/1WX1IjB) por Lionel Levine.
[/schedule]

Puntos alcanzables en un mapa

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

Definir las funciones

tales que

  • (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

  • (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Soluciones

El problema de las N torres

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

representa una solución del problema de las 3 torres.

Definir las funciones

tales que
+ (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

  • (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

Soluciones

[schedule expon=’2018-06-12′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 17 de abril.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2018-06-12′ at=»06:00″]

[/schedule]

Números de Church

Los números naturales pueden definirse de forma alternativa empleando los números de Church. Podemos representar un número natural n como una función que toma una función f como parámetro y devuelve n veces f.

Definimos por tanto los números naturales como

De esta forma, para representar el número uno, repetir una vez una función es lo mismo que solamente aplicarla.

De manera similar, dos debe aplicar f dos veces a su argumento.

Definir cero equivale por tanto a devolver el argumento sin modificar.

Definir las funciones

tales que

  • cero, uno y dos son definiciones alternativas a las ya dadas y tres es el número natural 3 con esta representación.
  • (nat2Int n) es el número entero correspondiente al número natuaral n. Por ejemplo,

  • (succ n) es el sucesor del número n. Por ejemplo,

  • (suma n m) es la suma de n y m. Por ejemplo,

  • (mult n m) es el producto de n y m. Por ejemplo,

  • (exp n m) es la potencia m-ésima de n. Por ejemplo,

Comprobar con QuickCheck las siguientes propiedades. Para ello importar la librería Test.QuickCheck.Function y seguir el siguiente ejemplo:

Nota 1: Añadir al inicio del archivo del ejercicio los pragmas

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

Caminos reducidos

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

Definir la función

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

Nótese que en el penúltimo ejemplo las reducciones son

Soluciones

Problema de las 3 jarras

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

tales que

  • (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

  • (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

Soluciones

Sucesión de Recamán

La sucesión de Recamán está definida como sigue:

Definir las funciones

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
    Sucesion_de_Recaman_1
  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja
    Sucesion_de_Recaman_2
    y (graficaInvRecaman 100) dibuja
    Sucesion_de_Recaman_3

Soluciones

Problema de las jarras

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

La interpretación de la solución anterior es

Otros ejemplos:

Soluciones

Mayor número de atracciones visitables

En el siguiente gráfico se representa en una cuadrícula el plano de Manhattan. Cada línea es una opción a seguir; el número representa las atracciones que se pueden visitar si se elige esa opción.

El turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. Sólo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).

Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = nº de atracciones si se va hacia el sur y b = nº de atracciones si se va al este. Además, ponemos un 0 en el valor del número de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:

En este caso, si se hace el recorrido

el número de atracciones es

cuya suma es 34.

Definir la función

tal que (mayorNumeroV p) es el máximo número de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por

entonces

Para los siguientes ejemplos se define un generador de mapas

Entonces,

Soluciones

Operaciones con series de potencias

Una serie de potencias es una serie de la forma

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

Definir las siguientes funciones

tales que

  • (opuesta xs) es la opuesta de la serie xs. Por ejemplo,

  • (suma xs ys) es la suma de las series xs e ys. Por ejemplo,

  • (resta xs ys) es la resta de las series xs es ys. Por ejemplo,

  • (producto xs ys) es el producto de las series xs e ys. Por ejemplo,

  • (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

  • (derivada xs) es la derivada de la serie xs. Por ejemplo,

  • (integral xs) es la integral de la serie xs. Por ejemplo,

  • expx es la serie de la función exponencial. Por ejemplo,

Soluciones

Números compuestos por un conjunto de primos

Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son

El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].

Definir la función

tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,

Soluciones

Notas de evaluación acumulada

La evaluación acumulada, las notas se calculan recursivamente con la siguiente función

donde E(k) es la nota del examen k. Por ejemplo, si las notas de los exámenes son [3,7,6,3] entonces las acumuladas son [3.0,7.0,6.4,4.4]

Las notas e los exámenes se encuentran en ficheros CSV con los valores separados por comas. Cada línea representa la nota de un alumno, el primer valor es el identificador del alumno y los restantes son sus notas. Por ejemplo, el contenido de examenes.csv es

Definir las funciones

tales que

  • (acumuladas xs) es la lista de las notas acumuladas (redondeadas con un decimal) de los notas de los exámenes xs. Por ejemplo,

  • (notasAcumuladas f1 f2) que escriba en el fichero f2 las notas acumuladas correspondientes a las notas de los exámenes del fichero f1. Por ejemplo, al evaluar

escribe en el fichero acumuladas.csv

Soluciones

Cálculo de pi mediante la serie de Nilakantha

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es
Calculo_de_pi_mediante_la_serie_de_Nilakantha

Definir las funciones

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

  • (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

al evaluar la expresión

hace que el contenido del fichero «AproximacionesPi.txt» sea

Soluciones

La conjetura de Gilbreath

Partiendo de los 5 primeros números primos y calculando el valor absoluto de la diferencia de cada dos números consecutivos hasta quedarse con un único número se obtiene la siguiente tabla:

Se observa que todas las filas, salvo la inicial, comienzan con el número 1.

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

Se observa que, de nuevo, todas las filas, salvo la inicial, 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.

El objetivo de este ejercicio es comprobar experimentalmente dicha conjetura.

Para la representación, usaremos la simétrica de la que hemos comentado anteriormente; es decir,

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).

Definir las siguientes funciones

tales que

  • (siguiente x ys) es la línea siguiente de la ys que empieza por x en la tabla de Gilbreath; es decir, si ys es [y1,y2,…,yn], entonces (siguiente x ys) es [x,|y1-x|,|y2-|y1-x||,…] Por ejemplo,

  • triangulo es el triángulo de Gilbreath. Por ejemplo,

  • (conjeturaGilbreath n) se verifica si se cumple la conjetura de Gilbreath para los n primeros números primos; es decir, en el triángulo de Gilbreath cuya primera columna son los n primeros números primos, todas las filas a partir de la segunda terminan en 1. Por ejemplo,

Soluciones

Vértices de un cuadrado

Definir la función

tal que (esCuadrado p q r s) se verifica si los puntos p, q, r y s son los vértices de un cuadrado. Por ejemplo,

Soluciones

Fractal hexagonal

Escribir, usando CodeWorld, un programa para dibujar el fractal hexagonal que se muestra en la siguiente animación
Fractal_hexagonal

Las 4 primeras fases de la animación son

  • Fase 0:
    Fractal_hexagonal_0
  • Fase 1:
    Fractal_hexagonal_1
  • Fase 2:
    Fractal_hexagonal_2
  • Fase 3:
    Fractal_hexagonal_3

Nota: Este ejercicio ha sido propuesto por Agustín Martín Aguera.

Soluciones

Suma de las hojas de mínimo nivel

Los árboles binarios con valores en las hojas y en los nodos se definen por

Por ejemplo, el árbol

se pueden representar por

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

Soluciones

Bosque de recorridos del autobús

En la librería Data.Tree se definen los árboles y los bosques como sigue

Se pueden definir árboles. Por ejemplo,

También se pueden definir bosques. Por ejemplo,

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

en donde la última rama representa el recorrido [(2,0),(2,2),(2,2)].

Soluciones

Caminos minimales en un árbol numérico

En la librería Data.Tree se definen los árboles y los bosques como sigue

Se pueden definir árboles. Por ejemplo,

Y se pueden dibujar con la función drawTree. Por ejemplo,

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

Definir las siguientes funciones

tales que

  • (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

Soluciones

Sumas de dos cuadrados

Definir la función

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

Soluciones

[/schedule]