Los números racionales pueden representarse mediante pares de números enteros. Por ejemplo, el número 2/5 puede representarse mediante el par (2,5).

Definir las funciones

   formaReducida    :: (Int,Int) -> (Int,Int)
   sumaRacional     :: (Int,Int) -> (Int,Int) -> (Int,Int)
   productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)
   igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool

tales que

• formaReducida x es la forma reducida del número racional x. Por ejemplo,

     formaReducida (4,10)  ==  (2,5)
     formaReducida (0,5)   ==  (0,1)

• sumaRacional x y es la suma de los números racionales x e y, expresada en forma reducida. Por ejemplo,

     sumaRacional (2,3) (5,6)  ==  (3,2)
     sumaRacional (3,5) (-3,5) ==  (0,1)

• productoRacional x y es el producto de los números racionales x e y, expresada en forma reducida. Por ejemplo,

     productoRacional (2,3) (5,6)  ==  (5,9)

• igualdadRacional x y se verifica si los números racionales x e y son iguales. Por ejemplo,

     igualdadRacional (6,9) (10,15)  ==  True
     igualdadRacional (6,9) (11,15)  ==  False
     igualdadRacional (0,2) (0,-5)   ==  True

Comprobar con QuickCheck la propiedad distributiva del producto racional respecto de la suma.

Leer más…

Los intervalos cerrados se pueden representar mediante una lista de dos números (el primero es el extremo inferior del intervalo y el segundo el superior).

Definir la función

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

tal que (interseccion i1 i2) es la intersección de los intervalos i1 e i2. Por ejemplo,

   interseccion [] [3,5]     ==  []
   interseccion [3,5] []     ==  []
   interseccion [2,4] [6,9]  ==  []
   interseccion [2,6] [6,9]  ==  [6,6]
   interseccion [2,6] [0,9]  ==  [2,6]
   interseccion [2,6] [0,4]  ==  [2,4]
   interseccion [4,6] [0,4]  ==  [4,4]
   interseccion [5,6] [0,4]  ==  []

Comprobar con QuickCheck que la intersección de intervalos es conmutativa.

Leer más…

La fórmula de Herón, descubierta por Herón de Alejandría, dice que el área de un triángulo cuyo lados miden a, b y c es la raíz cuadrada de s(s-a)(s-b)(s-c) donde s es el semiperímetro

   s = (a+b+c)/2

Definir la función

   area :: Double -> Double -> Double -> Double

tal que (area a b c) es el área del triángulo de lados a, b y c. Por ejemplo,

   area 3 4 5  ==  6.0

Leer más…

Definir la función

   raices :: Double -> Double -> Double -> [Double]

tal que (raices a b c) es la lista de las raíces reales de la ecuación [latex]ax^2 + bx + c = 0[/latex]. Por ejemplo,

   raices 1 3 2    ==  [-1.0,-2.0]
   raices 1 (-2) 1 ==  [1.0,1.0]
   raices 1 0 1    ==  []

Comprobar con QuickCheck que la suma de las raíces de la ecuación [latex]ax^2 + bx + c = 0[/latex] (con [latex]a[/latex] no nulo) es [latex]\dfrac{-b}{a}[/latex] y su producto es [latex]\dfrac{c}{a}[/latex].

Leer más…

Definir la función

   numeroDeRaices :: (Num t, Ord t) => t -> t -> t -> Int

tal que (numeroDeRaices a b c) es el número de raíces reales de la ecuación [latex]ax^2 + bx + c = 0[/latex]. Por ejemplo,

   numeroDeRaices 2 0 3    ==  0
   numeroDeRaices 4 4 1    ==  1
   numeroDeRaices 5 23 12  ==  2

Leer más…

Definir la función

   numeroMayor :: Int -> Int -> Int

tal que (numeroMayor x y) es el mayor número de dos cifras que puede construirse con los dígitos x e y. Por ejemplo,

   numeroMayor 2 5 ==  52
   numeroMayor 5 2 ==  52

Leer más…

Definir la función

   ciclo :: [a] -> [a]

tal que (ciclo xs) es la lista obtenida permutando cíclicamente los elementos de la lista xs, pasando el último elemento al principio de la lista. Por ejemplo,

   ciclo [2,5,7,9]  == [9,2,5,7]
   ciclo []         == []
   ciclo [2]        == [2]

Comprobar que la longitud es un invariante de la función ciclo; es decir, la longitud de (ciclo xs) es la misma que la de xs.

Leer más…

Definir la función

   distancia :: (Double,Double) -> (Double,Double) -> Double

tal que (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por ejemplo,

   distancia (1,2) (4,6)  ==  5.0

Comprobar con QuickCheck que se verifica la propiedad triangular de la distancia; es decir, dados tres puntos p1, p2 y p3, la distancia de p1 a p3 es menor o igual que la suma de la distancia de p1 a p2 y la de p2 a p3.

Leer más…

Definir la función

   intercambia :: (a,b) -> (b,a)

tal que (intercambia p) es el punto obtenido intercambiando las coordenadas del punto p. Por ejemplo,

   intercambia (2,5)  ==  (5,2)
   intercambia (5,2)  ==  (2,5)

Leer más…

Las dimensiones de los rectángulos puede representarse por pares; por ejemplo, (5,3) representa a un rectángulo de base 5 y altura 3.

Definir la función

   mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)

tal que (mayorRectangulo r1 r2) es el rectángulo de mayor área entre r1 y r2. Por ejemplo,

   mayorRectangulo (4,6) (3,7)  ==  (4,6)
   mayorRectangulo (4,6) (3,8)  ==  (4,6)
   mayorRectangulo (4,6) (3,9)  ==  (3,9)

Leer más…

La disyunción excluyente de dos fórmulas se verifica si una es verdadera y la otra es falsa. Su tabla de verdad es

   x     | y     | xor x y
   ------+-------+---------
   True  | True  | False
   True  | False | True
   False | True  | True
   False | False | False

Definir la función

   xor :: Bool -> Bool -> Bool

tal que (xor x y) es la disyunción excluyente de x e y. Por ejemplo,

   xor True  True  == False
   xor True  False == True
   xor False True  == True
   xor False False == False

Leer más…

Definir la función

   divisionSegura :: Double -> Double -> Double

tal que (divisionSegura x y) es x/y si y no es cero y 9999 en caso contrario. Por ejemplo,

   divisionSegura 7 2  ==  3.5
   divisionSegura 7 0  ==  9999.0

Leer más…

Definir la función

   tresDiferentes :: Int -> Int -> Int -> Bool

tal que (tresDiferentes x y z) se verifica si los elementos x, y y z son distintos. Por ejemplo,

   tresDiferentes 3 5 2  ==  True
   tresDiferentes 3 5 3  ==  False

Leer más…

Definir la función

   tresIguales :: Int -> Int -> Int -> Bool

tal que (tresIguales x y z) se verifica si los elementos x, y y z son iguales. Por ejemplo,

   tresIguales 4 4 4  ==  True
   tresIguales 4 3 4  ==  False

Leer más…

Definir la función

   mediano :: Int -> Int -> Int -> Int

tal que (mediano x y z) es el número mediano de los tres números x, y y z. Por ejemplo,

   mediano 3 2 5  ==  3
   mediano 2 4 5  ==  4
   mediano 2 6 5  ==  5
   mediano 2 6 6  ==  6

Leer más…

Definir la función

   extremos :: Int -> [a] -> [a]

tal que (extremos n xs) es la lista formada por los n primeros elementos de xs y los n finales elementos de xs. Por ejemplo,

   extremos 3 [2,6,7,1,2,4,5,8,9,2,3]  ==  [2,6,7,9,2,3]

Leer más…

Definir la función

   segmento :: Int -> Int -> [a] -> [a]

tal que (segmento m n xs) es la lista de los elementos de xs comprendidos entre las posiciones m y n. Por ejemplo,

   segmento 3 4 [3,4,1,2,7,9,0]  ==  [1,2]
   segmento 3 5 [3,4,1,2,7,9,0]  ==  [1,2,7]
   segmento 5 3 [3,4,1,2,7,9,0]  ==  []

Leer más…

Definir la función

   finales :: Int -> [a] -> [a]

tal que (finales n xs) es la lista formada por los n finales elementos de xs. Por ejemplo,

   finales 3 [2,5,4,7,9,6]  ==  [7,9,6]

Leer más…

Definir la función

   interior :: [a] -> [a]

tal que (interior xs) es la lista obtenida eliminando los extremos de la lista xs. Por ejemplo,

   interior [2,5,3,7,3]  ==  [5,3,7]
   interior [2..7]       ==  [3,4,5,6]

Leer más…

Definir la función

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

tal que (palindromo xs) se verifica si xs es un palíndromo; es decir, es lo mismo leer xs de izquierda a derecha que de derecha a izquierda. Por ejemplo,

   palindromo [3,2,5,2,3]    ==  True
   palindromo [3,2,5,6,2,3]  ==  False

Leer más…

Definir la función

   rango :: [Int] -> [Int]

tal que (rango xs) es la lista formada por el menor y mayor elemento de xs. Por ejemplo,

   rango [3,2,7,5]  ==  [2,7]

Leer más…

Definir la función

   rota :: Int -> [a] -> [a]

tal que (rota n xs) es la lista obtenida poniendo los n primeros elementos de xs al final de la lista. Por ejemplo,

   rota 1 [3,2,5,7]  ==  [2,5,7,3]
   rota 2 [3,2,5,7]  ==  [5,7,3,2]
   rota 3 [3,2,5,7]  ==  [7,3,2,5]

Leer más…

Definir la función

   rota1 :: [a] -> [a]

tal que (rota1 xs) es la lista obtenida poniendo el primer elemento de xs al final de la lista. Por ejemplo,

   rota1 [3,2,5,7]  ==  [2,5,7,3]

Leer más…

Definir la función

   maxTres :: Int -> Int -> Int -> Int

tal que (maxTres x y z) es el máximo de x, y y z. Por ejemplo,

   maxTres 6 2 4  ==  6
   maxTres 6 7 4  ==  7
   maxTres 6 7 9  ==  9

Leer más…

Definir la función

   ultimoDigito :: Int -> Int

tal que (ultimoDigito x) es el último dígito del número x. Por ejemplo,

   ultimoDigito 325  ==  5

Leer más…

Definir la función

   areaDeCoronaCircular :: Double -> Double -> Double

tal que (areaDeCoronaCircular r1 r2) es el área de una corona circular de radio interior r1 y radio exterior r2. Por ejemplo,

   areaDeCoronaCircular 1 2 == 9.42477796076938
   areaDeCoronaCircular 2 5 == 65.97344572538566
   areaDeCoronaCircular 3 5 == 50.26548245743669

Leer más…

Definir la función

   volumenEsfera :: Double -> Double

tal que (volumenEsfera r) es el volumen de la esfera de radio r. Por ejemplo,

   volumenEsfera 10  ==  4188.790204786391

Leer más…

Definir la función

   sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a

tal que (sumaSiTodosJustos xs) es justo la suma de todos los elementos de xs si todos son justos (es decir, si Nothing no pertenece a xs) y Nothing en caso contrario. Por ejemplo,

   sumaSiTodosJustos [Just 2, Just 5]           == Just 7
   sumaSiTodosJustos [Just 2, Just 5, Nothing]  == Nothing

Leer más…

Definir la función

   media3 :: Float -> Float -> Float -> Float

tal que (media3 x y z) es la media aritmética de los números x, y y z. Por ejemplo,

   media3 1 3 8     ==  4.0
   media3 (-1) 0 7  ==  2.0
   media3 (-3) 0 3  ==  0.0

Leer más…

Mañana comenzará en en este blog un curso práctico de introducción a la programación con Haskell y Python.

Diariamente, se publicará un ejercicio con sus soluciones en Haskell y en Python. El orden de los ejercicios se corresponde con el de los temas del curso de Programación funcional con Haskell. Además, en cada ejercicio se comentarán las diferencias entre ambos lenguajes y se irá extendiendo la tabla de equivalencia entre Haskell y Python.

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]
λ> sumasDeDosPrimos !! (5*10^5)
862878

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…

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 (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). 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 :: [[Int]]

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]]

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.

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 sucesivamente 1, 9, 1, 9, ... 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..10^6], esBelga 0 n]  ==  272049

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…

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 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…

La indicatriz de Euler (también 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
length (show (phi (10^(10^5)))) == 100000

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

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 (sucSumaCuadradosDigitos1 2000)
[2000,4,16,37,58,89,145,42,20,4,16,37,58,89,145,42,20,4,16,37]
λ> 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 2000 !! (10^9)
20

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 !! 3000  ==  7778521

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

Leer más…

Las primeras sumas alternas de los factoriales son números primos; en efecto,

3! - 2! + 1! = 5
4! - 3! + 2! - 1! = 19
5! - 4! + 3! - 2! + 1! = 101
6! - 5! + 4! - 3! + 2! - 1! = 619
7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899

son primos, pero

9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981

no es primo.

Definir las funciones

sumaAlterna         :: Integer -> Integer
sumasAlternas       :: [Integer]
conSumaAlternaPrima :: [Integer]

tales que

• (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,

sumaAlterna 3  ==  5
sumaAlterna 4  ==  19
sumaAlterna 5  ==  101
sumaAlterna 6  ==  619
sumaAlterna 7  ==  4421
sumaAlterna 8  ==  35899
sumaAlterna 9  ==  326981
sumaAlterna (5*10^4) `mod` (10^6) == 577019

• sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,

λ> take 10 sumasAlternas1
[0,1,1,5,19,101,619,4421,35899,326981]

• conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,

λ> take 8 conSumaAlternaPrima
[3,4,5,6,7,8,10,15]

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^3 + n^2p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8^3 + 8^2×19 = 12^3.

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 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: 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 :: Ord a => [(a,a)] -> [(a,a)]

tal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a 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)]
λ> length (clausuraTransitiva [(n,n+1) | n <- [1..100]])
5050

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

Definir la función

transitiva :: Ord 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
transitiva [(n,n) | n <- [1..10^4]]         ==  True

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 :: Ord 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)]

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

Leer más…

Definir la función

numeroParticiones :: Int -> Int -> Int

tal que (numeroParticiones n k) es el número de particiones de conjunto de n elementos en k subconjuntos disjuntos. Por ejemplo,

numeroParticiones 3 2    ==  3
numeroParticiones 3 3    ==  1
numeroParticiones 4 3    ==  6
numeroParticiones 4 1    ==  1
numeroParticiones 4 4    ==  1
numeroParticiones 91 89  ==  8139495

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]]]

Leer más…

Un número semiprimo es un número natural es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2·13) y 49 también lo es (porque 49 = 7·7).

Definir la función

mayorSemiprimoMenor :: Integer -> Integer

tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,

mayorSemiprimoMenor 27      ==  26
mayorSemiprimoMenor 50      ==  49
mayorSemiprimoMenor 49      ==  46
mayorSemiprimoMenor (10^15) == 999999999999998

Leer más…

Definir la función

interseccionParcial :: Ord a => Int -> [[a]] -> [a]

tal que (interseccionParcial n xss) es la lista de los elementos que pertenecen al menos a n conjuntos de xss. Por ejemplo,

interseccionParcial 1 [[3,4],[4,5,9],[5,4,7]]  == [3,4,5,9,7]
interseccionParcial 2 [[3,4],[4,5,9],[5,4,7]]  == [4,5]
interseccionParcial 3 [[3,4],[4,5,9],[5,4,7]]  == [4]
interseccionParcial 4 [[3,4],[4,5,9],[5,4,7]]  == []

Leer más…

Definir las funciones

unionGeneral        :: Eq a => [[a]] -> [a]
interseccionGeneral :: Eq a => [[a]] -> [a]

tales que

• (unionGeneral xs) es la unión de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a alguno de los elementos de xs). Por ejemplo,

unionGeneral []                    ==  []
unionGeneral [[1]]                 ==  [1]
unionGeneral [[1],[1,2],[2,3]]     ==  [1,2,3]
unionGeneral ([[x] | x <- [1..9]]) ==  [1,2,3,4,5,6,7,8,9]

• (interseccionGeneral xs) es la intersección de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a todos los elementos de xs). Por ejemplo,

interseccionGeneral [[1]]                      ==  [1]
interseccionGeneral [[2],[1,2],[2,3]]          ==  [2]
interseccionGeneral [[2,7,5],[1,5,2],[5,2,3]]  ==  [2,5]
interseccionGeneral ([[x] | x <- [1..9]])      ==  []
interseccionGeneral (replicate (10^6) [1..5])  ==  [1,2,3,4,5]

Leer más…

Definir la función

cerosDelFactorial :: Integer -> Integer

tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

cerosDelFactorial 24                         == 4
cerosDelFactorial 25                         == 6
length (show (cerosDelFactorial (10^70000))) == 70000

Leer más…

Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a "0", 2 dígitos iguales a "1", 1 dígito igual a "2" y ningún dígito igual a "3".

Definir la función

autodescriptivo :: Integer -> Bool

tal que (autodescriptivo n) se verifica si n es autodescriptivo. Por ejemplo,

λ> autodescriptivo 1210
True
λ> [x | x <- [1..100000], autodescriptivo x]
[1210,2020,21200]
λ> autodescriptivo 9210000001000
True

Leer más…

Una forma de aproximar el número π es usando la siguiente igualdad: \[ \frac{\pi}{2} = 1 + \frac{1}{3} + \frac{1 \cdot 2}{3 \cdot 5} + \frac{1 \cdot 2 \cdot 3}{3 \cdot 5 \cdot 7} + \frac{1 \cdot 2 \cdot 3 \cdot 4}{3 \cdot 5 \cdot 7 \cdot 9} + \cdots \]

Es decir, la serie cuyo término general n-ésimo es el cociente entre el producto de los primeros n números y los primeros n números impares: \[ s(n) = \frac{\prod\limits_{i=1}^n i}{\prod\limits_{i=1}^n (2i + 1)} \]

Definir la función

aproximaPi :: Integer -> Double

tal que (aproximaPi n) es la aproximación del número π calculada con la serie anterior hasta el término n-ésimo. Por ejemplo,

aproximaPi 10     == 3.1411060206
aproximaPi 20     == 3.1415922987403397
aproximaPi 30     == 3.1415926533011596
aproximaPi 40     == 3.1415926535895466
aproximaPi 50     == 3.141592653589793
aproximaPi (10^4) == 3.141592653589793
pi                == 3.141592653589793

Leer más…

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la lista

pandigitalesPrimos :: [Int]

tal que sus elementos son los números pandigitales primos, ordenados de mayor a menor. Por ejemplo,

take 3 pandigitalesPrimos       ==  [7652413,7642513,7641253]
2143 `elem` pandigitalesPrimos  ==  True
length pandigitalesPrimos       ==  538

Leer más…

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que

n = d(0)·F(2) + d(1)·F(3) +...+ d(k-1)·F(k+1)
d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Por ejemplo, la codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y

1·F(2) + 0·F(3) + 1·F(4) = 1·1 + 0·2 + 1·3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

 1  = 1     = F(2)           ≡       11
 2  = 2     = F(3)           ≡      011
 3  = 3     = F(4)           ≡     0011
 4  = 1+3   = F(2)+F(4)      ≡     1011
 5  = 5     = F(5)           ≡    00011
 6  = 1+5   = F(2)+F(5)      ≡    10011
 7  = 2+5   = F(3)+F(5)      ≡    01011
 8  = 8     = F(6)           ≡   000011
 9  = 1+8   = F(2)+F(6)      ≡   100011
10  = 2+8   = F(3)+F(6)      ≡   010011
11  = 3+8   = F(4)+F(6)      ≡   001011
12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
13  = 13    = F(7)           ≡  0000011
14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

λ> codigoFib 65
"0100100011"
λ> [codigoFib n | n <- [1..7]]
["11","011","0011","1011","00011","10011","01011"]

Comprobar con QuickCheck las siguientes propiedades:

• Todo entero positivo se puede descomponer en suma de números de la sucesión de Fibonacci.
• Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
• En las codificaciones de Fibonacci, la cadena "11" sólo aparece una vez y la única vez que aparece es al final.

Leer más…

La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la sucesión de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

cuyos elementos son los términos de la sucesión anterior. Por ejemplo,

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]
λ> (reloj !! 1000) `mod` (10^50)
23432123432123432123432123432123432123432123432123

Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.

Leer más…

El método de bisección para calcular un cero de una función en el intervalo [a,b] se basa en el teorema de Bolzano:

"Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0".

El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:

• Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
• Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
• Si no, repetir el proceso en el intervalo [c,b].

Definir la función

biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,

biseccion (\x -> x^2 - 3) 0 5 0.01             ==  1.7333984375
biseccion (\x -> x^3 - x - 2) 0 4 0.01         ==  1.521484375
biseccion cos 0 2 0.01                         ==  1.5625
biseccion (\x -> log (50-x) - 4) (-10) 3 0.01  ==  -5.125

Leer más…

Un número n es especial si mcm(1,2,...,n-1) = mcm(1,2,...,n). Por ejemplo, el 6 es especial ya que

mcm(1,2,3,4,5) = 60 = mcm(1,2,3,4,5,6)

Definir la sucesión

especiales :: [Integer]

cuyos términos son los números especiales. Por ejemplo,

take 10 especiales     ==  [1,6,10,12,14,15,18,20,21,22]
especiales !! 50       ==  84
especiales !! 500      ==  638
especiales !! 5000     ==  5806
especiales !! 50000    ==  55746

Leer más…

Definir la función

suma :: Integer -> Integer

tal que (suma n) es la suma 1·1! + 2·2! + 3·3! + ... + n·n!. Por ejemplo,

suma 1  ==  1
suma 2  ==  5
suma 3  ==  23
suma 4  ==  119
suma 5  ==  719
take 9 (show (suma 70000))  ==  "823780458"

Leer más…

La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo usando la fórmula \[ h \cdot \left( f\left(a + \frac{h}{2}\right) + f\left(a + h + \frac{h}{2}\right) + f\left(a + 2h + \frac{h}{2}\right) + \dots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a + n h + \frac{h}{2} \leq b < a + (n+1) h + \frac{h}{2} \] y usando valores pequeños para \(h\).

Definir la función

integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a

tal que (integral a b f h) es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de f(x) = x^3 entre 0 y 1, con paso 0.01, es

integral 0 1 (^3) 0.01  ==  0.24998750000000042

Otros ejemplos son

integral 0 1 (^4) 0.01                   ==  0.19998333362500048
integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01  ==  1.9999250000000026
log 2 - integral 1 2 (\x -> 1/x) 0.01         ==  3.124931644782336e-6
pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01  ==  -8.333333331389525e-6

Leer más…

El menor número con 2 divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 4 divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 8 divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

Definir la función

menor :: Integer -> Integer

tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,

menor 1  ==  2
menor 2  ==  6
menor 3  ==  24
menor 4  ==  120
length (show (menor (4*10^4)))  ==  207945

Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.

Leer más…

Definir, por simulación, la función

distanciaEsperada :: Int -> IO Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

distanciaEsperada 10     ==  0.43903617921423593
distanciaEsperada 10     ==  0.6342350621260004
distanciaEsperada 100    ==  0.5180418995364429
distanciaEsperada 100    ==  0.5288261085653962
distanciaEsperada 1000   ==  0.5143804432569616
distanciaEsperada 10000  ==  0.5208360147922616

El valor exacto de la distancia esperada es \[ ve = \frac{\sqrt{2} + 2 + 5 \log(1 + \sqrt{2})}{15} \approx 0.5214054331647207 \]

Definir la función

graficaDistanciaEsperada :: [Int] -> IO ()

tal que (graficaDistanciaEsperada ns) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja

Leer más…

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

type Relacion = ([Int],[(Int,Int)])
type Matriz = Array (Int,Int) Bool

Definir la función

matrizRB:: Relacion -> Matriz

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])
array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),
((2,1),False),((2,2),False),((2,3),False),
((3,1),True) ,((3,2),False),((3,3),True)]
λ> matrizRB ([1..3],[(1,3), (3,1)])
array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),
((2,1),False),((2,2),False),((2,3),False),
((3,1),True) ,((3,2),False),((3,3),False)]
λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
False

Leer más…

Dada una lista de números naturales xs, codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es \[2^7 \times 3^1 \times 5^5 = 1200000 \]

Definir las funciones

codificaG   :: [Integer] -> Integer
decodificaG :: Integer -> [Integer]

tales que

• (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,

codificaG [6,0,4]            ==  1200000
codificaG [3,1,1]            ==  3600
codificaG [3,1,0,0,0,0,0,1]  ==  4423058640
codificaG [1..6]             ==  126111168580452537982500

• (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,

decodificaG 1200000                   ==  [6,0,4]
decodificaG 3600                      ==  [3,1,1]
decodificaG 4423058640                ==  [3,1,0,0,0,0,0,1]
decodificaG 126111168580452537982500  ==  [1,2,3,4,5,6]

Comprobar con QuickCheck que ambas funciones son inversas; es decir,

decodificaG (codificaG xs) = xs
codificaG (decodificaG n) = n

Leer más…

Un primo circular es un número tal que todas las rotaciones de dígitos producen números primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus dígitos son 197, 971 y 719 y los tres números son primos.

Definir la lista

circulares :: [Integer]

cuyo valor es la lista de los números primos circulares. Por ejemplo,

take 16 circulares == [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,197]
circulares !! 50   == 933199

Leer más…

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000