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
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)]
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)]
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ón4*(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
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
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
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
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
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]
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
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
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
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]
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
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]]
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.
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
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
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
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
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] == []
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
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] == []
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.
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
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
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.
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.
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
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].
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
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
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.
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.
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)
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)
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
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
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
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
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
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]
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] == []
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]
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]
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
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]
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]
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]
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
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
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
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
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
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
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.
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 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 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]]
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.
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 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.
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
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
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 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
λ> take 10 sumasAlternas1 [0,1,1,5,19,101,619,4421,35899,326981]
λ> take 8 conSumaAlternaPrima [3,4,5,6,7,8,10,15]
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
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]
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
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
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.
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
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]]]
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
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]] == []
Definir las funciones
unionGeneral :: Eq a => [[a]] -> [a] interseccionGeneral :: Eq a => [[a]] -> [a]
tales que
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 [[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]
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
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
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
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
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:
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.
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:
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
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
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"
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
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.
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
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
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
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
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
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
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.
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.
Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:
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
En este ejercicio, representamos las fracciones mediante pares de números de enteros.
Definir la función
fraccionesOrd :: Integer -> [(Integer,Integer)]
tal que (fraccionesOrd n) es la lista con las fracciones propias positivas ordenadas, con denominador menor o igual que n. Por ejemplo,
λ> fraccionesOrd 4 [(1,4),(1,3),(1,2),(2,3),(3,4)] λ> fraccionesOrd 5 [(1,5),(1,4),(1,3),(2,5),(1,2),(3,5),(2,3),(3,4),(4,5)]
En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n = 40, 40²+40+41 = 40(40+1)+41 es divisible por 41.
Usando ordenadores, se descubrió que el polinomio n² - 79n + 1601 genera 80 números primos para todos los valores de n entre 0 y 79.
Definir la función
generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])
tal que (generadoresMaximales n) es el par (m,xs) donde
xs es la lista de pares (x,y) tales que n²+xn+y es uno de polinomios que genera un número máximo de números primos consecutivos a partir de cero entre todos los polinomios de la forma n²+an+b, con |a| ≤ n y |b| ≤ n ym es dicho número máximo.Por ejemplo,
generadoresMaximales 4 == ( 3,[(-2,3),(-1,3),(3,3)]) generadoresMaximales 6 == ( 5,[(-1,5),(5,5)]) generadoresMaximales 41 == (41,[(-1,41)]) generadoresMaximales 50 == (43,[(-5,47)]) generadoresMaximales 100 == (48,[(-15,97)]) generadoresMaximales 200 == (53,[(-25,197)]) generadoresMaximales 1650 == (80,[(-79,1601)])
El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Definir la función
trianguloFloyd :: [[Integer]]
tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,
λ> take 4 trianguloFloyd [[1], [2,3], [4,5,6], [7,8,9,10]] (trianguloFloyd !! (10^5)) !! 0 == 5000050001 (trianguloFloyd !! (10^6)) !! 0 == 500000500001 (trianguloFloyd !! (10^7)) !! 0 == 50000005000001
La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
La colocación de los elementos se puede ver gráficamente en este enlace.
Definir la función
zigZag :: Int -> Matrix Int
tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,
λ> zigZag 5 ┌ ┐ │ 0 1 5 6 14 │ │ 2 4 7 13 15 │ │ 3 8 12 16 21 │ │ 9 11 17 20 22 │ │ 10 18 19 23 24 │ └ ┘ λ> zigZag 4 ┌ ┐ │ 0 1 5 6 │ │ 2 4 7 12 │ │ 3 8 11 13 │ │ 9 10 14 15 │ └ ┘ λ> maximum (zigZag 1500) 2249999
