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

data Arbol a = H
             | N a (Arbol a) (Arbol a)
             deriving (Eq, Show)

Por ejemplo, el árbol

       3
      / \
     /   \
    4     7
   / \   / \
  5   0 0   3
 / \
2   0

se representa por

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente

        3-0
        / \
       /   \
      /     \
    4-1     7-1
    / \     / \
  5-2 0-2 0-2 3-0
  / \
2-3 0-3

Definir la función

anotado :: Arbol a -> Arbol (a,Int)

tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,

λ> anotado ejArbol
N (3,0)
  (N (4,1)
     (N (5,2) (H (2,3)) (H (0,3)))
     (H (0,2)))
  (N (7,1) (H (0,2)) (H (3,2)))

Leer más…

Definir la función

compactada :: [Maybe Int] -> [Int]

tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:

1. se eliminan los elementos Nothing;
2. si dos elementos consecutivos tienen el mismo valor, se sustituyen por el sucesor de su valor y
3. los restantes elementos no se cambian.

Por ejemplo,

λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]
[2,5,3,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]
[2,1,4,3,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]
[2,1,5,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]
[2,1,4,3,4]
λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
[2,2,4,3,4]

Leer más…

Definir la función

sinEspaciosExtremos :: String -> String

tal que (sinEspaciosExtremos cs) es la cadena obtenida eliminando los espacios blancos de los extremos de la cadena cs. Por ejemplo,

λ> sinEspaciosExtremos "   El lunes a las 12:30.     "
"El lunes a las 12:30."

Leer más…

Sea \( n \) un número natural cuya factorización prima es \[ n = 2^a \cdot p_1^{b_1} \cdots p_n^{b_n} \cdot q_1^{c_1} \cdots q_m^{c_m} \] donde los \( p_i \) son los divisores primos de \( n \) congruentes con \( 3 \) módulo \( 4 \) y los \( q_j \) son los divisores primos de \( n \) congruentes con \( 1 \) módulo \( 4 \). Entonces, el número de formas de descomponer \( n \) como suma de dos cuadrados es \( 0 \), si algún \( b_i \) es impar y es el techo (es decir, el número entero más próximo por exceso) de \[ \frac{(1+c_1) \cdots (1+c_m)}{2} \] en caso contrario. Por ejemplo, el número \( 2^3 \cdot (3^9 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) no se puede descomponer como sumas de dos cuadrados (porque el exponente de \( 3 \) es impar) y el número \( 2^3 \cdot (3^2 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) tiene \( 14 \) descomposiciones como suma de dos cuadrados (porque los exponentes de \( 3 \) y \( 7 \) son pares y el techo de \( \frac{(1+3)(1+6)}{2} \) es \( 14 \)).

Definir la función

   nRepresentaciones :: Integer -> Integer

tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,

   nRepresentaciones (2^3*3^9*5^3*7^8*13^6)        ==  0
   nRepresentaciones (2^3*3^2*5^3*7^8*13^6)        ==  14
   head [n | n <- [1..], nRepresentaciones n > 8]  ==  71825

Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad

prop_nRepresentaciones :: Integer -> Property
prop_nRepresentaciones n =
    n > 0 ==>
      nRepresentaciones2 n == genericLength (representaciones n)

Leer más…

Definir la función

representaciones :: Integer -> [(Integer,Integer)]

tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.

representaciones  20           ==  [(2,4)]
representaciones  25           ==  [(0,5),(3,4)]
representaciones 325           ==  [(1,18),(6,17),(10,15)]
representaciones 100000147984  ==  [(0,316228)]

Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.

Leer más…

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...

Definir la función

factorizacionesH :: Integer -> [[Integer]]

tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,

factorizacionesH  25  ==  [[5,5]]
factorizacionesH  45  ==  [[5,9]]
factorizacionesH 441  ==  [[9,49],[21,21]]

Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque laa factorización, como para el 441, puede no ser única).

Leer más…

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...

Definir la sucesión

primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

take 15 primosH  == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
primosH !! 20000 == 203221

Leer más…

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

[0]
[0,1]
[0,1,1,0]
[0,1,1,0,1,0,0,1]
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

De esta forma se va formando una sucesión

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...

que se conoce como la sucesión de Thue-Morse.

Definir la sucesión

sucThueMorse :: [Int]

cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,

λ> take 30 sucThueMorse
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
λ> map (sucThueMorse4 !!) [1234567..1234596]
[1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0]
λ> map (sucThueMorse4 !!) [4000000..4000030]
[1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]

Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces

s(2n)   = s(n)
s(2n+1) = 1 - s(n)

Leer más…

Definir la función

ordPorFrecuencia :: Ord a => [a] -> [a]

tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen menos a los que aparecen más. Por ejemplo,

ordPorFrecuencia "canalDePanama"  ==  "DPcelmnnaaaaa"
ordPorFrecuencia "20012016"       ==  "61122000"

Leer más…

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

1. Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
2. Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
3. Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
4. Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
5. Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
6. mcd(a,0) = a
7. mcd(0,b) = b
8. mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

mcd(660,420)
= 2*mcd(330,210)    [por 1]
= 2*2*mcd(165,105)  [por 1]
= 2*2*mcd(30,105)   [por 4]
= 2*2*mcd(15,105)   [por 2]
= 2*2*mcd(15,45)    [por 4]
= 2*2*mcd(15,15)    [por 4]
= 2*2*15            [por 8]
= 60

Definir la función

mcd :: Integer -> Integer -> Integer

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

mcd 660 420  ==  60
mcd 3 0      ==  3
mcd 0 3      ==  3

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Leer más…

Definir la función

agrupa :: (a -> Bool) -> [a] -> [[a]]

tal que (agrupa p xs) es la lista obtenida separando los elementos consecutivos de xs que verifican la propiedad p de los que no la verifican. Por ejemplo,

agrupa odd   [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa even  [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa (> 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1,2,0,4],[9,6],[4],[5,7],[2]]
agrupa (< 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[1,2,0],[4,9,6,4,5,7],[2]]

Comprobar con QuickCheck que para cualquier propiedad p y cualquier lista xs, la concatenación de (agrupa p xs) es xs; es decir,

prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
prop_agrupa (Blind p) xs =
    concat (agrupa1 p xs) == xs

Nota. Usar la librería Test.QuickCheck.Modifiers.

Leer más…

Definir la sucesión

sumasDeDosPrimos :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,

λ> take 23 sumasDeDosPrimos
[4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]

Leer más…

Los árboles binarios con datos en nodos y hojas se definen por

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

Por ejemplo, el árbol

       3
      / \
     /   \
    4     7
   / \   / \
  5   0 0   3
 / \
2   0

se representa por

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Definir la función

sucesores :: Arbol a -> [(a,[a])]

tal que (sucesores t) es la lista de los pares formados por los elementos del árbol t junto con sus sucesores. Por ejemplo,

λ> sucesores ejArbol
[(3,[4,7]),(4,[5,0]),(5,[2,0]),(2,[]),(0,[]),(0,[]),
 (7,[0,3]),(0,[]),(3,[])]

Leer más…

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

• [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
• [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
• [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir la función

funciones :: [a] -> [a] -> [[(a,a)]]

tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,

λ> funciones [] [2,4,6]
[[]]
λ> funciones [3] [2,4,6]
[[(3,2)],[(3,4)],[(3,6)]]
λ> funciones [1,3] [2,4,6]
[[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)],
 [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]

Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones
+++ OK, passed 100 tests.

Leer más…

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

[0]
[0,1]
[0,1,1,0]
[0,1,1,0,1,0,0,1]
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

Definir la lista

serieThueMorse :: [[Integer]]

tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,

λ> take 4 serieThueMorse
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

Comprobar con QuickCheck que cada término de la serie de Thue-Morse se obtiene del anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1.

Leer más…

Definir la función

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de lista de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)
[[2,3],[3,5],[5,7],[41,43],[43,47]]
λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)
[[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]
λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)
[[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]
λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50
[129197,129209,129221,129223]

Leer más…

Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n. Por ejemplo,

• El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, ... Como se alcanza el 18, resulta que el 18 es 0-belga.
• El 19 no es 1-belga, porque a partir del 1 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, ... Como no se alcanza el 19, resulta que el 19 no es 1-belga.

Definir la función

esBelga :: Int -> Int -> Bool

tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,

esBelga 0 18                              ==  True
esBelga 1 19                              ==  False
esBelga 0 2016                            ==  True
[x | x <- [0..30], esBelga 7 x]           ==  [7,10,11,21,27,29]
[x | x <- [0..30], esBelga 10 x]          ==  [10,11,20,21,22,24,26]
length [n | n <- [1..9000], esBelga 0 n]  ==  2857

Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.

Leer más…

Definir la función

antiimagen :: (Int -> Int) -> Int -> Maybe Int

tal que (antiimagen f y) es justo el x tal que f(x) = y, si y pertenece a la imagen de la función creciente f, o nada, en caso contrario. Por ejemplo,

antiimagen (^2) 25  ==  Just 5
antiimagen (^3) 25  ==  Nothing

Nota. Se supone que f está definida sobre los números naturales.

Leer más…

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

0 0 0 0 0    1 0 0 1 0
0 0 0 0 0    1 0 0 1 0
0 0 0 1 0    1 1 1 1 1
1 0 0 0 0    1 1 1 1 1
0 0 0 0 0    1 0 0 1 0

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

ej :: Matriz
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

Definir la función

relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

λ> elems (relleno ej)
[1,0,0,1,0,
 1,0,0,1,0,
 1,1,1,1,1,
 1,1,1,1,1,
 1,0,0,1,0]

Leer más…

Definir la sucesión

primosCon2016 :: [Integer]

tal que sus elementos son los números primos que contienen al 2016. Por ejemplo,

take 5 primosCon2016  ==  [20161,120163,120167,201611,201623]
primosCon2016 !! 111  ==  3020167

Leer más…

El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son

Primo Hueco
 2    1
 3    2
 7    4
11    2

El hueco de un número primo p es maximal si es mayor que los huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es

Primo Hueco
  2    1
  3    2
  7    4
 23    6
 89    8
113   14
523   18
887   20

Definir la sucesión

primosYhuecosMaximales :: [(Integer,Integer)]

cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,

λ> take 8 primosYhuecosMaximales
[(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]
λ> primosYhuecosMaximales !! 20
(2010733,148)

Leer más…

En lógica matemática, un literal es una fórmula atómica o su negación. Se puede definir por el tipo de dato

data Literal = Atom String
             | Neg Literal
             deriving (Eq, Show)

Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom "p") y (Neg (Atom "q")), respectivamente.

Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.

Definir la función

tautologia :: [Literal] -> Bool

tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]
True
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]
False
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]
False

Leer más…

La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.

Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.

El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).

Definir la función

nVisibles :: Integer -> Integer

tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,

nVisibles 6       ==  23
nVisibles 10      ==  63
nVisibles 100     ==  6087
nVisibles 1000    ==  608383
nVisibles 10000   ==  60794971
nVisibles 100000  ==  6079301507

Leer más…

En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).

Definir la función

nCambios :: (Num a, Ord a) => [a] -> Int

tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,

nCambios []                          ==  0
nCambios [6,5,-4,0,-2,-7,0,-8,-1,4]  ==  2
nCambios [6,5,-4,0, 2,-7,0,-8,-1,4]  ==  4

Leer más…

La parte libre de cuadrados de un número n es el producto de todos sus divisores primos con exponente impar en la factorización prima de n. Por ejemplo, la parte libre de cuadrados de 360 es 10 ya que 360 = 2³3²5 y 2.5 = 10; además, 360 = 10.6²

La parte cuadrada de un número n es el mayor número cuadrado que divide a n. Por ejemplo, la parte cuadrada de 360 es 6.

Definir las funciones

parteLibre    :: Integer -> Integer
parteCuadrada :: Integer -> Integer

tales que

• (parteLibre x) es la parte libre de x. Por ejemplo,

parteLibre 360                 ==  10
parteLibre 1800                ==  2
[parteLibre n | n <- [1..14]]  ==  [1,2,3,1,5,6,7,2,1,10,11,3,13,14]

• (parteCuadrada x) es la parte cuadrada de x. Por ejemplo,

parteCuadrada 360                 ==  36
parteCuadrada 1800                ==  900
[parteCuadrada n | n <- [1..14]]  ==  [1,1,1,4,1,1,1,4,9,1,1,4,1,1]

Leer más…

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.

Definir la función

phi :: Integer -> Integer

tal que (phi n) es igual a φ(n). Por ejemplo,

phi 36                     ==  12
map phi [10..20]           ==  [4,10,4,12,6,8,8,16,6,18,8]
phi (3^10^5) `mod` (10^9)  ==  681333334

Comprobar con QuickCheck que, para todo n > 0, φ(10ⁿ) tiene n dígitos.

Leer más…

Las fórmulas proposicionales construidas con las constantes verdadero (⊤), falso (⊥), las variables proposicionales y las conectivas de negación (¬), conjunción (∧) y disyunción (∨) se pueden definir usando el siguiente tipo de datos

data Prop = Const Bool
          | Var Char
          | Neg Prop
          | Conj Prop Prop
          | Disj Prop Prop
          deriving (Eq, Show)

Por ejemplo, la fórmula (A ∧ ⊥) ∨ (⊤ ∧ B) se representa por

Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))

La fórmula dual de una fórmula p es la fórmula obtenida intercambiando en p las ∧ por ∨ y también las ⊤ por ⊥. Por ejemplo, la dual de (A ∧ ⊥) ∨ (⊤ ∧ B) es (A ∨ ⊤) ∧ (⊥ ∨ B)

Definir la función

dual :: Prop -> Prop

tal que (dual p) es la dual de p. Por ejemplo,

λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B')))
Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))

Leer más…

Definir la función

sucSumaCuadradosDigitos :: Integer -> [Integer]

tal que (sucSumaCuadradosDigitos n) es la sucesión cuyo primer término es n y los restantes se obtienen sumando los cuadrados de los dígitos de su término anterior. Por ejemplo,

λ> take 20 (sucSumaCuadradosDigitos 2016)
[2016,41,17,50,25,29,85,89,145,42,20,4,16,37,58,89,145,42,20,4]
λ> take 20 (sucSumaCuadradosDigitos 1976)
[1976,167,86,100,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
λ> sucSumaCuadradosDigitos 2016 !! (10^8)
145

Leer más…

Definir la función

puntos :: Integer -> [(Integer,Integer)]

tal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de la cuadrícula [1..n]x[1..n] (es decir, 1 ≤ x,y ≤ n) tales que |x²-xy-y²| = 1. Por ejemplo,

length (puntos 10)          ==  5
length (puntos 100)         ==  10
length (puntos 1000)        ==  15
length (puntos (10^50000))  ==  239249

Leer más…

Un entero positivo n es un número práctico si todos los enteros positivos menores que él se pueden expresar como suma de distintos divisores de n. Por ejemplo, el 12 es un número práctico, ya que todos los enteros positivos menores que 12 se pueden expresar como suma de divisores de 12 (1, 2, 3, 4 y 6) sin usar ningún divisor más de una vez en cada suma:

 1 = 1
 2 = 2
 3 = 3
 4 = 4
 5 = 2 + 3
 6 = 6
 7 = 1 + 6
 8 = 2 + 6
 9 = 3 + 6
10 = 4 + 6
11 = 1 + 4 + 6

En cambio, 14 no es un número práctico ya que 6 no se puede escribir como suma, con sumandos distintos, de divisores de 14.

Definir la función

esPractico :: Integer -> Bool

tal que (esPractico n) se verifica si n es un número práctico. Por ejemplo,

esPractico 12                                      ==  True
esPractico 14                                      ==  False
esPractico 2016                                    ==  True
esPractico 42535295865117307932921825928971026432  ==  True

Leer más…

Definir las funciones

sumaRedondeos       :: Integer -> [Integer]
limiteSumaRedondeos :: Integer -> Integer

tales que

• (sumaRedondeos n) es la sucesión cuyo k-ésimo término es

redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

Por ejemplo,

take 5 (sumaRedondeos 1000)  ==  [500,750,875,937,968]

• (limiteSumaRedondeos n) es la suma de la serie

redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

Por ejemplo,

limiteSumaRedondeos1 2000                    ==  1999
limiteSumaRedondeos1 2016                    ==  2016
limiteSumaRedondeos5 (10^308) `mod` (10^10)  ==  123839487

Leer más…

Definir la función

optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

tal que (optimos r f xs) es la lista de los elementos de xs donde la función f alcanza sus valores óptimos respecto de la relación r. Por ejemplo,

optimos (<) length ["ab","c","de","f"]  ==  ["c","f"]
optimos (>) length ["ab","c","de","f"]  ==  ["ab","de"]

Leer más…

Definir la función

maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

tal que (maximales r xs) es la lista de los elementos de xs para los que no hay ningún otro elemento de xs mayor según la relación r. Por ejemplo,

maximales (>) [2,3,4,6]                     ==  [6]
maximales (<) [2,3,4,6]                     ==  [2]
maximales (\x y -> mod x y == 0) [2,3,4,6]  ==  [4,6]
maximales (\x y -> mod y x == 0) [2,3,4,6]  ==  [2,3]

Leer más…

Definir la función

esAnterior :: Eq a => [a] -> a -> a -> Bool

tal que (esAnterior xs y z) se verifica si y ocurre en xs antes que z (que puede no pertenecer a xs). Por ejemplo,

esAnterior [1,3,7,2] 3 2  ==  True
esAnterior [1,3,7,2] 3 1  ==  False
esAnterior [1,3,7,2] 3 5  ==  True
esAnterior [1,3,7,2] 5 3  ==  False

Leer más…

Definir la función

todosPares :: (a -> b -> c) -> [a] -> [b] -> [c]

tal que (todosPares f xs ys) es el resultado de aplicar la operación f a todos los pares de xs e ys. Por ejemplo,

todosPares (*) [2,3,5] [7,11]            == [14,22,21,33,35,55]
todosPares (\x y -> x:show y) "ab" [7,5] == ["a7","a5","b7","b5"]

Leer más…

Definir la función

inserta :: [a] -> [[a]] -> [[a]]

tal que (inserta xs yss) es la lista obtenida insertando

• el primer elemento de xs como primero en la primera lista de yss,
• el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos un elemento),
• el tercer elemento de xs como tercero en la tercera lista de yss (si la tercera lista de yss tiene al menos dos elementos),

y así sucesivamente. Por ejemplo,

inserta [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,3,8]]
inserta [1,2,3] [[4,7],[] ,[9,5,8]]  ==  [[1,4,7],[],   [9,5,3,8]]
inserta [1,2]   [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,8]]
inserta [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[6,2]]
inserta "tad"   ["odo","pra","naa"]  ==  ["todo","para","nada"]

Leer más…

Definir el procedimiento

arbol :: Int -> IO ()

tal que (arbol n) dibuja el árbol de Navidad con una copa de altura n y un tronco de altura la mitad de n. Por ejemplo,

λ> arbol 5

     X
    XXX
   XXXXX
  XXXXXXX
 XXXXXXXXX
     X
     X

λ> arbol 6

      X
     XXX
    XXXXX
   XXXXXXX
  XXXXXXXXX
 XXXXXXXXXXX
      X
      X
      X

λ> arbol 7

       X
      XXX
     XXXXX
    XXXXXXX
   XXXXXXXXX
  XXXXXXXXXXX
 XXXXXXXXXXXXX
       X
       X
       X

Leer más…

Definir la función

siembra :: [Int] -> [Int]

tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,

siembra [4]      ==  [0,1,1,1,1]
siembra [0,2]    ==  [0,0,1,1]
siembra [4,2]    ==  [0,1,2,2,1]

El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son

siembra [0,4,2]          ==  [0,0,1,2,2,1]
siembra [3]              ==  [0,1,1,1]
siembra [3,4,2]          ==  [0,1,2,3,2,1]
siembra [3,2,1]          ==  [0,1,2,3]
sum $ siembra [1..2500]  ==  3126250

Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.

Nota: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.

Leer más…

Definir la función

productoInfinito :: [Int] -> [Int]

tal que (productoInfinito xs) es la lista infinita que en la posición N tiene el producto de los N primeros elementos de la lista infinita xs. Por ejemplo,

take 5 (productoInfinito [1..])    ==  [1,2,6,24,120]
take 5 (productoInfinito [2,4..])  ==  [2,8,48,384,3840]
take 5 (productoInfinito [1,3..])  ==  [1,3,15,105,945]

Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Leer más…

Una lista hermanada es una lista de números estrictamente positivos en la que cada elemento tiene algún factor primo en común con el siguiente, en caso de que exista, o alguno de los dos es un 1. Por ejemplo,

• [2,6,3,9,1,5] es una lista hermanada pues 2 y 6 tienen un factor en común (2); 6 y 3 tienen un factor en común (3); 3 y 9 tienen un factor en común (3); de 9 y 1 uno es el número 1; y de 1 y 5 uno es el número 1.
• [2,3,5] no es una lista hermanada pues 2 y 3 no tienen ningún factor primo en común.

Definir la función

hermanada :: [Int] -> Bool

tal que (hermanada xs) se verifica si la lista xs es hermanada según la definición anterior. Por ejemplo,

hermanada [2,6,3,9,1,5]   ==  True
hermanada [2,3,5]         ==  False
hermanada [2,4..1000000]  ==  True

Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Leer más…

Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son

4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵,
36 = 6², 49 = 7², 64 = 2⁶, ...

Definir la sucesión

potenciasPerfectas :: [Integer]

cuyos términos son las potencias perfectas. Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 100   ==  6724

Definir el procedimiento

grafica :: Int -> IO ()

tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja

!Potencias perfectas](/images/Potencias_perfectas.png)

Leer más…

Definir la función

sumaEnPosicion :: [Int] -> [Int] -> Int

tal que (sumaEnPosicion xs ys) es la suma de todos los elementos de xs cuyas posiciones se indican en ys. Por ejemplo,

sumaEnPosicion [1,2,3] [0,2]  ==  4
sumaEnPosicion [4,6,2] [1,3]  ==  6
sumaEnPosicion [3,5,1] [0,1]  ==  8

Leer más…

Definir la función

factorizable :: Integer -> [Integer] -> Bool

tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,

factorizable 1  [2,5,6]                           ==  True
factorizable 12 [2,5,3]                           ==  True
factorizable 12 [2,5,6]                           ==  True
factorizable 12 [7,5,12]                          ==  True
factorizable 12 [2,3,1]                           ==  True
factorizable 12 [2,3,0]                           ==  True
factorizable 24 [12,4,6]                          ==  True
factorizable 0  [2,3,0]                           ==  True
factorizable 12 [5,6]                             ==  False
factorizable 12 [2,5,1]                           ==  False
factorizable 0  [2,3,5]                           ==  False
factorizable (product [1..3000])     [1..100000]  ==  True
factorizable (1 + product [1..3000]) [1..100000]  ==  False

Leer más…

Leer más…

El año 2016 será un año cúbico porque se puede escribir como la suma de los cubos de 7 números consecutivos; en efecto,

2016 = 3³+ 4³ +...+ 9³

Definir la función

esCubico :: Integer -> Bool

tal que (esCubico x) se verifica si x se puede escribir como la suma de los cubos de 7 números consecutivos. Por ejemplo,

esCubico 2016                ==  True
esCubico 2017                ==  False
esCubico 189005670081900441  ==  True
esCubico 189005670081900442  ==  False

Leer más…

Un primo con cubo es un número primo p para el que existe algún entero positivo n tal que la expresión n³ + n²p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8³ + 8²×19 = 12³.

Definir la sucesión

primosConCubos :: [Integer]

tal que sus elementos son los primos con cubo. Por ejemplo,

λ> take 6 primosConCubos
[7,19,37,61,127,271]
λ> length (takeWhile (< 1000000) primosConCubos)
173

Leer más…

Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.

Definir la sucesión

cubanos :: [Integer]

tal que sus elementos son los números cubanos. Por ejemplo,

λ> take 15 cubanos
[7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]

Leer más…

La clausura transitiva de una relación binaria R es la menor relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S (definida en el ejercicio del lunes): sea

R = [(1,2),(2,5),(5,6)]

la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea

R1 = R ∪ (R ∘ R)
= [(1,2),(2,5),(5,6),(1,5),(2,6)]

la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea

R2 = R1 ∪ (R1 ∘ R1)
= [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]

La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.

Definir la función

clausuraTransitiva :: Eq a => Rel a -> Rel a

tal que (clausuraTransitiva r) es la clausura transitiva de r. Por ejemplo,

λ> clausuraTransitiva [(1,2),(2,5),(5,6)]
[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]
[(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]

Leer más…

Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el

Definir la función

transitiva :: Eq a => [(a,a)] -> Bool

tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,

transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True
transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False

Leer más…

Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por

[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]

La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.

Definir la función

composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]

tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,

λ> composicion [(1,2)] [(2,3),(2,4)]
[(1,3),(1,4)]
λ> composicion [(1,2),(5,2)] [(2,3),(2,4)]
[(1,3),(1,4),(5,3),(5,4)]
λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]
[(1,3)]
λ> composicion [(0,1)] [(2,3)]
[]

Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.

Leer más…

Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que

22  = 2*11 y
2+2 = 2+(1+1)

y el 4937775 también lo es ya que

4937775       = 3*5*5*65837 y
4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7)

Definir las funciones

esSmith :: Integer -> Bool
smith :: [Integer]

tales que

• (esSmith x) se verifica si x es un número de Smith. Por ejemplo,

esSmith 22          ==  True
esSmith 29          ==  False
esSmith 2015        ==  False
esSmith 4937775     ==  True
esSmith 4567597056  ==  True

• smith es la lista cuyos elementos son los números de Smith. Por ejemplo,

λ> take 17 smith
[4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391]
λ> smith !! 2000
62158

Leer más…

Un número de n dígitos es un número de Armstrong si es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo, 371, 8208 y 4210818 son números de Armstrong ya que

    371 = 3^3 + 7^3 + 1^3
   8208 = 8^4 + 2^4 + 0^4 + 8^4
4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7

Definir las funciones

esArmstrong :: Integer -> Bool
armstrong :: [Integer]

tales que

• (esArmstrong x) se verifica si x es un número de Armstrong. Por ejemplo,

esArmstrong 371                                      ==  True
esArmstrong 8208                                     ==  True
esArmstrong 4210818                                  ==  True
esArmstrong 2015                                     ==  False
esArmstrong 115132219018763992565095597973971522401  ==  True
esArmstrong 115132219018763992565095597973971522402  ==  False

• armstrong es la lista cuyos elementos son los números de Armstrong. Por ejemplo,

λ> take 18 armstrong
[1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]

Comprobar con QuickCheck que los números mayores que 115132219018763992565095597973971522401 no son números de Armstrong.

Leer más…

Definir la sucesión

raicesEnterasDePrimos :: [Integer]

cuyos elementos son las partes enteras de las raíces cuadradas de los números primos. Por ejemplo,

λ> take 30 raicesEnterasDePrimos
[1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10,10]
λ> raicesEnterasDePrimos !!  9963
322
λ> raicesEnterasDePrimos !!  9964
323

Comprobar con QuickCheck que la diferencia entre dos términos consecutivos de la sucesión es como máximo igual a 1.

Leer más…

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

data Arbol a = H a
              | N a (Arbol a) (Arbol a)
              deriving Show

Por ejemplo, el árbol

     5
    / \
   /   \
  9     7
 / \   / \
1   4 6   8

se puede representar por

N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

Decimos que un árbol binario es par si la mayoría de sus nodos son pares e impar en caso contrario.

Para representar la paridad se define el tipo Paridad

data Paridad = Par | Impar deriving (Eq, Show)

Definir la función

paridad :: Arbol3 Int -> Paridad

tal que (paridad a) es la paridad del árbol a. Por ejemplo,

paridad (N 8 (N 6 (H 3) (H 4)) (H 5))  ==  Par
paridad (N 8 (N 9 (H 3) (H 4)) (H 5))  ==  Impar

Leer más…

Definir las funciones

separacion :: [a] -> ([a],[a])
mezcla     :: ([a],[a]) -> [a]

tales que (separacion xs) es el par formado eligiendo alternativamente elementos de xs mientras que mezcla intercala los elementos de las dos listas. Por ejemplo,

separacion [1..5]                   ==  ([1,3,5],[2,4])
mezcla ([1,3,5],[2,4])              ==  [1,2,3,4,5]
separacion "Telescopio"             ==  ("Tlsoi","eecpo")
mezcla ("Tlsoi","eecpo")            ==  "Telescopio"
take 5 (fst (separacion [2,4..]))   ==  [2,6,10,14,18]
take 6 (mezcla ([2,4..],[7,14..]))  ==  [2,7,4,14,6,21]

Comprobar con QuickCheck que

mezcla (separacion xs) == xs

Leer más…

Definir la función

particiones :: [a] -> Int -> [[[a]]]

tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,

λ> particiones [2,3,6] 2
[[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]]
λ> particiones [2,3,6] 3
[[[2],[3],[6]]]
λ> particiones [4,2,3,6] 3
[[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]],
 [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]]
λ> particiones [4,2,3,6] 1
[[[4,2,3,6]]]
λ> particiones [4,2,3,6] 4
[[[4],[2],[3],[6]]]