Algoritmo de Euclides del mcd

José A. Alonso

Definiciones por recursión

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = mcd (b, a módulo b), si b > 0

Definir la función

   mcd :: Integer -> Integer -> Integer

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

   mcd 30 45  ==  15
   mcd 45 30  ==  15

Comprobar con QuickCheck que el máximo común divisor de dos números a y b (ambos mayores que 0) es siempre mayor o igual que 1 y además es menor o igual que el menor de los números a y b.

Potencia entera

José A. Alonso

Definiciones por recursión

Definir la función

   potencia :: Integer -> Integer -> Integer

tal que potencia x n es x elevado al número natural n. Por ejemplo,

   potencia 2 3  ==  8

Base de dato de actividades

José A. Alonso

Definiciones por comprensión

Las bases de datos sobre actividades de personas pueden representarse mediante listas de elementos de la forma (a,b,c,d), donde a es el nombre de la persona, b su actividad, c su fecha de nacimiento y d la de su fallecimiento. Un ejemplo es la siguiente que usaremos a lo largo de este ejercicio,

   personas :: [(String,String,Int,Int)]
   personas = [("Cervantes","Literatura",1547,1616),
               ("Velazquez","Pintura",1599,1660),
               ("Picasso","Pintura",1881,1973),
               ("Beethoven","Musica",1770,1823),
               ("Poincare","Ciencia",1854,1912),
               ("Quevedo","Literatura",1580,1654),
               ("Goya","Pintura",1746,1828),
               ("Einstein","Ciencia",1879,1955),
               ("Mozart","Musica",1756,1791),
               ("Botticelli","Pintura",1445,1510),
               ("Borromini","Arquitectura",1599,1667),
               ("Bach","Musica",1685,1750)]

Definir las funciones

   nombres   :: [(String,String,Int,Int)] -> [String]
   musicos   :: [(String,String,Int,Int)] -> [String]
   seleccion :: [(String,String,Int,Int)] -> String -> [String]
   musicos'  :: [(String,String,Int,Int)] -> [String]
   vivas     :: [(String,String,Int,Int)] -> Int -> [String]

tales que

nombres bd es la lista de los nombres de las personas de la base de datos bd. Por ejemplo,

     λ> nombres personas
     ["Cervantes","Velazquez","Picasso","Beethoven","Poincare",
      "Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",
      "Bach"]

musicos bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos personas  ==  ["Beethoven","Mozart","Bach"]

seleccion bd m es la lista de los nombres de las personas de la base de datos bd cuya actividad es m. Por ejemplo,

     λ> seleccion personas "Pintura"
     ["Velazquez","Picasso","Goya","Botticelli"]
     λ> seleccion personas "Musica"
     ["Beethoven","Mozart","Bach"]

musicos' bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos' personas  ==  ["Beethoven","Mozart","Bach"]

vivas bd a es la lista de los nombres de las personas de la base de datos bd que estaban vivas en el año a. Por ejemplo,

     λ> vivas personas 1600
     ["Cervantes","Velazquez","Quevedo","Borromini"]

Representación densa de polinomios

José A. Alonso

Definiciones por comprensión

Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio \(6x^4-5x^2+4x-7\) se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].

Definir la función

   densa :: [Int] -> [(Int,Int)]

tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,

   densa [6,0,-5,4,-7]  ==  [(4,6),(2,-5),(1,4),(0,-7)]
   densa [6,0,0,3,0,4]  ==  [(5,6),(2,3),(0,4)]
   densa [0]            ==  [(0,0)]

Suma elementos consecutivos

José A. Alonso

Definiciones por comprensión

Definir la función

   sumaConsecutivos :: [Integer] -> [Integer]

tal que sumaConsecutivos xs es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,

   sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
   sumaConsecutivos [3]        ==  []
   last (sumaConsecutivos [1..10^8])  ==  199999999

Producto escalar

José A. Alonso

Definiciones por comprensión

El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.

Definir la función

   productoEscalar :: [Integer] -> [Integer] -> Integer

tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,

   productoEscalar [1,2,3] [4,5,6]  ==  32

Ternas pitagóricas con suma dada

José A. Alonso

Definiciones por comprensión

Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

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

tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

   ternasPitagoricas 12     == [(3,4,5)]
   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Ternas pitagórica

José A. Alonso

Definiciones por comprensión

Una terna (x,y,z) de enteros positivos es pitagórica si x² + y² = z² y x < y < z.

Definir la función

   pitagoricas :: Int -> [(Int,Int,Int)]

tal que pitagoricas n es la lista de todas las ternas pitagóricas cuyas componentes están entre 1 y n. Por ejemplo,

   pitagoricas 10  ==  [(3,4,5),(6,8,10)]
   pitagoricas 15  ==  [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]

Cálculo del número π mediante la fórmula de Leibniz

José A. Alonso

Definiciones por comprensión

El número π puede calcularse con la fórmula de Leibniz

   π/4 = 1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1) + ...

Definir las funciones

   calculaPi :: Int -> Double
   errorPi   :: Double -> Int

tales que

calculaPi n es la aproximación del número π calculada mediante la expresión

     4*(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1))

Por ejemplo,

     calculaPi 3    ==  2.8952380952380956
     calculaPi 300  ==  3.1449149035588526

errorPi x es el menor número de términos de la serie necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1    ==    9
     errorPi 0.01   ==   99
     errorPi 0.001  ==  999

Aproximación al límite de sen(x)/x cuando x tiende a cero

José A. Alonso

Definiciones por comprensión

El limite de sen(x)/x, cuando x tiende a cero, se puede calcular como el límite de la sucesión sen(1/n)/(1/n), cuando n tiende a infinito.

Definir las funciones

   aproxLimSeno :: Int -> [Double]
   errorLimSeno :: Double -> Int

tales que

aproxLimSeno n es la lista de los n primeros términos de la sucesión sen(1/m)/(1/m). Por ejemplo,

     aproxLimSeno 1 == [0.8414709848078965]
     aproxLimSeno 2 == [0.8414709848078965,0.958851077208406]

errorLimSeno x es el menor número de términos de la sucesión sen(1/m)/(1/m) necesarios para obtener su límite con un error menor que x. Por ejemplo,

     errorLimSeno 0.1     ==   2
     errorLimSeno 0.01    ==   5
     errorLimSeno 0.001   ==  13
     errorLimSeno 0.0001  ==  41

Aproximación del número e

José A. Alonso

Definiciones por comprensión

El número e se define como el límite de la sucesión [latex]\left(1+\dfrac{1}{n}\right)^n[/latex].

Definir las funciones

   aproxE      :: Int -> [Double]
   errorAproxE :: Double -> Int

tales que

aproxE k es la lista de los k primeros términos de la sucesión. Por ejemplo,

     aproxE 4 == [2.0,2.25,2.37037037037037,2.44140625]
     last (aproxE (7*10^7))  ==  2.7182818287372563

errorE x es el menor número de términos de la sucesión necesarios para obtener su límite con un error menor que x. Por ejemplo,

     errorAproxE 0.1    ==  13
     errorAproxE 0.01   ==  135
     errorAproxE 0.001  ==  1359

Puntos en el círculo

José A. Alonso

Definiciones por comprensión

En el círculo de radio 2 hay 6 puntos cuyas coordenadas son puntos naturales:

   (0,0),(0,1),(0,2),(1,0),(1,1),(2,0)

y en de radio 3 hay 11:

   (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)

Definir la función

   circulo :: Int -> Int

tal que circulo n es el la cantidad de pares de números naturales (x,y) que se encuentran en el círculo de radio n. Por ejemplo,

   circulo 1    ==  3
   circulo 2    ==  6
   circulo 3    ==  11
   circulo 4    ==  17
   circulo 100  ==  7955

Suma de múltiplos de 3 ó 5

José A. Alonso

Definiciones por comprensión

Definir la función

   euler1 :: Integer -> Integer

tal que euler1 n es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

   euler1 10      == 23
   euler1 (10^2)  == 2318
   euler1 (10^3)  == 233168
   euler1 (10^4)  == 23331668
   euler1 (10^5)  == 2333316668
   euler1 (10^10) == 23333333331666666668
   euler1 (10^20) == 2333333333333333333316666666666666666668
   euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

Nota: Este ejercicio está basado en el problema 1 del Proyecto Euler

Números abundantes impares

José A. Alonso

Definiciones por comprensión

Definir la lista

  abundantesImpares :: [Integer]

cuyos elementos son los números abundantes impares. Por ejemplo,

   λ> take 12 abundantesImpares
   [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615]

Todos los abundantes hasta n son pares

José A. Alonso

Definiciones por comprensión

Definir la función

   todosPares :: Integer -> Bool

tal que todosPares n se verifica si todos los números abundantes menores o iguales que n son pares. Por ejemplo,

   todosPares 10    ==  True
   todosPares 100   ==  True
   todosPares 1000  ==  False

Números abundantes menores o iguales que n

José A. Alonso

Definiciones por comprensión

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numerosAbundantesMenores :: Integer -> [Integer]

tal que numerosAbundantesMenores n es la lista de números abundantes menores o iguales que n. Por ejemplo,

   numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
   numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
   length (numerosAbundantesMenores (10^6)) ==  247545

Números abundantes

José A. Alonso

Definiciones por comprensión

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numeroAbundante :: Int -> Bool

tal que numeroAbundante n se verifica si n es un número abundante. Por ejemplo,

   numeroAbundante 5  == False
   numeroAbundante 12 == True
   numeroAbundante 28 == False
   numeroAbundante 30 == True
   numeroAbundante 100000000  ==  True
   numeroAbundante 100000001  ==  False

Números perfectos

José A. Alonso

Definiciones por comprensión

Un números entero positivo es perfecto es igual a la suma de sus divisores, excluyendo el propio número. Por ejemplo, 6 es un número perfecto porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3.

Definir la función

   perfectos :: Integer -> [Integer]

tal que perfectos n es la lista de todos los números perfectos menores o iguales que n. Por ejemplo,

   perfectos 500     ==  [6,28,496]
   perfectos (10^5)  ==  [6,28,496,8128]

Suma de divisores

José A. Alonso

Definiciones por comprensión

Definir la función

   sumaDivisores :: Integer -> Integer

tal que sumaDivisores x es la suma de los divisores de x. Por ejemplo,

   sumaDivisores 12                 ==  28
   sumaDivisores 25                 ==  31
   sumaDivisores (product [1..25])  ==  93383273455325195473152000
   length (show (sumaDivisores (product [1..30000])))  ==  121289
   maximum (map sumaDivisores [1..2*10^6])             ==  8851392

Triángulo aritmético

José A. Alonso

Definiciones por comprensión

Los triángulos aritméticos se forman como sigue

    1
    2  3
    4  5  6
    7  8  9 10
   11 12 13 14 15
   16 17 18 19 20 21

Definir las funciones

   linea     :: Integer -> [Integer]
   triangulo :: Integer -> [[Integer]]

tales que

linea n es la línea n-ésima de los triángulos aritméticos. Por ejemplo,

     linea 4  ==  [7,8,9,10]
     linea 5  ==  [11,12,13,14,15]
     head (linea (10^20)) == 4999999999999999999950000000000000000001

triangulo n es el triángulo aritmético de altura n. Por ejemplo,

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

Suma de cuadrados menos cuadrado de la suma

José A. Alonso

Definiciones por comprensión

Definir la función

   euler6 :: Integer -> Integer

tal que euler6 n es la diferencia entre el cuadrado de la suma de los n primeros números y la suma de los cuadrados de los nprimeros números. Por ejemplo,

   euler6 10       ==  2640
   euler6 (10^10)  ==  2500000000166666666641666666665000000000

Nota: Este ejercicio está basado en el problema 6 del proyecto Euler.

Suma de los cuadrados de los primeros números naturales

José A. Alonso

Definiciones por comprensión

Definir la función

   sumaDeCuadrados :: Integer -> Integer

tal que sumaDeCuadrados n es la suma de los cuadrados de los primeros n números; es decir, 1² + 2² + ... + n². Por ejemplo,

   sumaDeCuadrados 3    ==  14
   sumaDeCuadrados 100  ==  338350
   length (show (sumaDeCuadrados (10^100)))  ==  300

Suma de los primeros números naturales

José A. Alonso

Definiciones por comprensión

Definir la función

   suma :: Integer -> Integer

tal suma n es la suma de los n primeros números. Por ejemplo,

   suma 3  ==  6
   length (show (suma (10^100)))  ==  200

Números libres de cuadrados

José A. Alonso

Definiciones por comprensión

Un número es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

tal que libreDeCuadrados x se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70  ==  True
   libreDeCuadrados 40  ==  False
   libreDeCuadrados (product (take 30000 primes))  ==  True

Divisores primos

José A. Alonso

Definiciones por comprensión

Definir la función

   divisoresPrimos :: Integer -> [Integer]

tal que divisoresPrimos x es la lista de los divisores primos de x. Por ejemplo,

   divisoresPrimos 40 == [2,5]
   divisoresPrimos 70 == [2,5,7]
   length (divisoresPrimos (product [1..20000])) == 2262

Diferencia conjuntista de listas

José A. Alonso

Definiciones por comprensión

Definir la función

   diferencia :: Eq a => [a] -> [a] -> [a]

tal que diferencia xs ys es la diferencia de las listas sin elementos repetidos xs e ys. Por ejemplo,

   diferencia [3,2,5,6] [5,7,3,4]  ==  [2,6]
   diferencia [3,2,5] [5,7,3,2]    ==  []

Divisores de un número

José A. Alonso

Definiciones por comprensión

Definir la función

   divisores :: Integer -> [Integer]

tal que divisores n es la lista de los divisores de n. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

Intersección conjuntista de listas

José A. Alonso

Definiciones por comprensión

Definir la función

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

tal que interseccion xs ys es la intersección de las listas sin elementos repetidos xs e ys. Por ejemplo,

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

Unión conjuntista de listas

José A. Alonso

Definiciones por comprensión

Definir la función

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

tal que union xs ys es la unión de las listas, sin elementos repetidos, xs e ys. Por ejemplo,

   union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]

Comprobar con QuickCheck que la unión es conmutativa.

Igualdad de conjuntos

José A. Alonso

Definiciones por comprensión

Definir la función

   iguales :: Ord a => [a] -> [a] -> Bool

tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. Por ejemplo,

   iguales [3,2,3] [2,3]    ==  True
   iguales [3,2,3] [2,3,2]  ==  True
   iguales [3,2,3] [2,3,4]  ==  False
   iguales [2,3] [4,5]      ==  False

Reconocimiento de subconjunto

José A. Alonso

Definiciones por comprensión

Definir la función

   subconjunto :: Ord a => [a] -> [a] -> Bool

tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. por ejemplo,

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

Números racionales

José A. Alonso

Definiciones elementales de funciones

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.

Intersección de intervalos cerrados

José A. Alonso

Definiciones elementales de funciones

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.

Fórmula de Herón para el área de un triángulo

José A. Alonso

Definiciones elementales de funciones

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

Raíces de la ecuación de segundo grado

José A. Alonso

Definiciones elementales de funciones

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

Número de raíces de la ecuación de segundo grado

José A. Alonso

Definiciones elementales de funciones

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

Mayor número con dos dígitos dados

José A. Alonso

Definiciones elementales de funciones

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

Permutación cíclica

José A. Alonso

Definiciones elementales de funciones

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.

Distancia entre dos puntos

José A. Alonso

Definiciones elementales de funciones

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.

Intercambio de componentes de un par

José A. Alonso

Definiciones elementales de funciones

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)

Mayor rectángulo

José A. Alonso

Definiciones elementales de funciones

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)

Disyunción excluyente

José A. Alonso

Definiciones elementales de funciones

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

División segura

José A. Alonso

Definiciones elementales de funciones

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

Tres diferentes

José A. Alonso

Definiciones elementales de funciones

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

Tres iguales

José A. Alonso

Definiciones elementales de funciones

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

Elemento mediano

José A. Alonso

Definiciones elementales de funciones

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

Primeros y últimos elementos

José A. Alonso

Definiciones elementales de funciones

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]

Segmento de una lista

José A. Alonso

Definiciones elementales de funciones

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

Elementos finales

José A. Alonso

Definiciones elementales de funciones

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]

Interior de una lista

José A. Alonso

Definiciones elementales de funciones

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]

Reconocimiento de palíndromos

José A. Alonso

Definiciones elementales de funciones

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

Rango de una lista

José A. Alonso

Definiciones elementales de funciones

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]

Los primeros al final

José A. Alonso

Definiciones elementales de funciones

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]

El primero al final

José A. Alonso

Definiciones elementales de funciones

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]

Máximo de tres números

José A. Alonso

Definiciones elementales de funciones

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

Último dígito

José A. Alonso

Definiciones elementales de funciones

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

Área de la corona circular

José A. Alonso

Definiciones elementales de funciones

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

Volumen de la esfera

José A. Alonso

Definiciones elementales de funciones

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

Suma si todos los valores son justos

José A. Alonso

Definiciones elementales de funciones

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

Media aritmética de tres números.

José A. Alonso

Definiciones elementales de funciones

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

Curso de introducción a la programación con Haskell y Python

José A. Alonso

Definiciones elementales de funciones

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.

Sumas de dos primos

José A. Alonso

Misceláneas

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

La sucesión de Thue-Morse

José A. Alonso

Misceláneas

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)

La serie de Thue-Morse

José A. Alonso

Misceláneas

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

Números belgas

José A. Alonso

Misceláneas

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.

Huecos maximales entre primos

José A. Alonso

Misceláneas

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)

La función indicatriz de Euler

José A. Alonso

Misceláneas

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.

Sucesión de suma de cuadrados de los dígitos

José A. Alonso

Misceláneas

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

Potencias perfectas

José A. Alonso

Misceláneas

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

Potencias perfectas

Sumas alternas de factoriales

José A. Alonso

Misceláneas

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]

Primos con cubos

José A. Alonso

Misceláneas

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

Primos cubanos

José A. Alonso

Misceláneas

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]

Clausura transitiva de una relación binaria

José A. Alonso

Misceláneas

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

Transitividad de una relación

José A. Alonso

Misceláneas

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

Composición de relaciones binarias

José A. Alonso

Misceláneas

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.

Número de particiones en k subconjuntos

José A. Alonso

Misceláneas

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

Particiones en k subconjuntos

José A. Alonso

Misceláneas

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

Mayor semiprimo menor que n

José A. Alonso

Misceláneas

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

Intersecciones parciales

José A. Alonso

Misceláneas

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

Unión e intersección general de conjuntos

José A. Alonso

Misceláneas

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]

Ceros finales del factorial

José A. Alonso

Misceláneas

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

Números autodescriptivos

José A. Alonso

Misceláneas

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

Aproximación del número pi

José A. Alonso

Misceláneas

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

Pandigitales primos

José A. Alonso

Misceláneas

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

Codificación de Fibonacci

José A. Alonso

Misceláneas

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.

La sucesión del reloj astronómico de Praga

José A. Alonso

Misceláneas

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.

Método de bisección para aproximar raíces de funciones

José A. Alonso

Misceláneas

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

Números para los que el mcm de 1,2,...n-1 coincide con el de 1,2,...,n

José A. Alonso

Misceláneas

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

Cálculo de la suma 1·1! + 2·2! + 3·3! + ... + n·n!

José A. Alonso

Misceláneas

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"

Cálculo aproximado de integrales definidas

José A. Alonso

Misceláneas

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

Menor número con una cantidad dada de divisores

José A. Alonso

Misceláneas

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.

Distancia esperada entre dos puntos de un cuadrado unitario

José A. Alonso

Misceláneas

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

Distancia esperada entre dos puntos de un cuadrado unitario

Representación matricial de relaciones binarias

José A. Alonso

Misceláneas

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

Codificación de Gödel

José A. Alonso

Misceláneas

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

Primos circulares

José A. Alonso

Misceláneas

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

Diccionario de frecuencias

José A. Alonso

Misceláneas

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

Descomposiciones con sumandos 1 ó 2

José A. Alonso

Misceláneas

Definir la funciones

sumas  :: Int -> [[Int]]
nSumas :: Int -> Integer

tales que

(sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

sumas 1            ==  [[1]]
sumas 2            ==  [[1,1],[2]]
sumas 3            ==  [[1,1,1],[1,2],[2,1]]
sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
length (sumas 26)  ==  196418
length (sumas 33)  ==  5702887

(nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

nSumas 4                      ==  5
nSumas 123                    ==  36726740705505779255899443
length (show (nSumas 123456)) ==  25801

Suma de los elementos de las diagonales matrices espirales

José A. Alonso

Misceláneas

Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales

|1 2|   |7 8 9|   | 7  8  9 10|   |21 22 23 24 25|
|4 3|   |6 1 2|   | 6  1  2 11|   |20  7  8  9 10|
        |5 4 3|   | 5  4  3 12|   |19  6  1  2 11|
                  |16 15 14 13|   |18  5  4  3 12|
                                  |17 16 15 14 13|

La suma los elementos de sus diagonales es

+ en la 2x2: 1+3+2+4               =  10
+ en la 3x3: 1+3+5+7+9             =  25
+ en la 4x4: 1+2+3+4+7+10+13+16    =  56
+ en la 5x5: 1+3+5+7+9+13+17+21+25 = 101

Definir la función

sumaDiagonales :: Integer -> Integer

tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.

sumaDiagonales 1         ==  1
sumaDiagonales 2         ==  10
sumaDiagonales 3         ==  25
sumaDiagonales 4         ==  56
sumaDiagonales 5         ==  101
sumaDiagonales (10^6)    ==  666667166668000000
sumaDiagonales (1+10^6)  ==  666669166671000001

sumaDiagonales (10^2)  ==         671800
sumaDiagonales (10^3)  ==        667168000
sumaDiagonales (10^4)  ==       666716680000
sumaDiagonales (10^5)  ==      666671666800000
sumaDiagonales (10^6)  ==     666667166668000000
sumaDiagonales (10^7)  ==    666666716666680000000
sumaDiagonales (10^8)  ==   666666671666666800000000
sumaDiagonales (10^9)  ==  666666667166666668000000000

Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.

Término ausente en una progresión aritmética

José A. Alonso

Misceláneas

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]               ==  5
ausente [3,5,9,11]               ==  7
ausente [3,5,7,11]               ==  9
ausente ([1..9]++[11..])         ==  10
ausente ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Polinomios de Bell

José A. Alonso

Misceláneas

Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:

B₀(x) = 1 (polinomio unidad)
Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)] (donde Bₙ'(x) es la derivada de Bₙ(x))

Por ejemplo,

B₀(x) = 1                     = 1
B₁(x) = x·(1+0)               = x
B₂(x) = x·(x+1)               = x²+x
B₃(x) = x·(x²+x+2x+1)         = x³+3x²+x
B₄(x) = x·(x³+3x²+x+3x²+6x+1) = x⁴+6x³+7x²+x

Definir la función

polBell :: Integer -> Polinomio Integer

tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,

polBell 4                    ==  x^4 + 6*x^3 + 7*x^2 + 1*x
coeficiente 2 (polBell 4)    ==  7
coeficiente 2 (polBell 30)   ==  536870911
coeficiente 1 (polBell 1000) == 1
length (show (coeficiente 9 (polBell 2000)))  ==  1903

Notas: Se usa la librería I1M.PolOperaciones. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por

coeficiente :: Num a => Int -> Polinomio a -> a
coeficiente k p | k == n                 = coefLider p
                | k > grado (restoPol p) = 0
                | otherwise              = coeficiente k (restoPol p)
                where n = grado p