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 constante
pandigitalesPrimos :: [Int]
tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,
take 3 pandigitalesPrimos == [7652413,7642513,7641253] 2143 `elem` pandigitalesPrimos == True length pandigitalesPrimos == 538
Definir la función
nMinimoCambios :: Ord a => [a] -> Int
tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,
nMinimoCambios [3,5,3,7,9,6] == 4 nMinimoCambios [3,5,3,7,3,3] == 2 nMinimoCambios "Salamanca" == 5 nMinimoCambios (4 : [1..500000]) == 499999
En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.
Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).
Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]
Definir las funciones
decimalAmultiple :: [Int] -> Int -> [Int] multipleAdecimal :: [Int] -> [Int] -> Int
tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,
decimalAmultiple [2,4..] 377 == [7,5,0,1] multipleAdecimal [2,4..] [7,5,0,1] == 377 decimalAmultiple [2,5..] 377 == [4,5,3,1] multipleAdecimal [2,5..] [4,5,3,1] == 377 decimalAmultiple [2^n | n <- [1..]] 2015 == [1,15,3,3,1] multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1] == 2015 decimalAmultiple (repeat 10) 2015 == [2,0,1,5] multipleAdecimal (repeat 10) [2,0,1,5] == 2015
Comprobar con QuickCheck que se verifican las siguientes propiedades
prop_inversas :: [Int] -> Int -> Property prop_inversas bs x = x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x prop_coeficientes :: [Int] -> Int -> Property prop_coeficientes bs x = x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs] where cs = reverse (decimalAmultiple bs x)
para distintas bases dadas. Por ejemplo,
λ> quickCheck (prop_inversas [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_inversas [3,5..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [3,5..]) +++ OK, passed 100 tests.
Definir la función
productos :: Integer -> Integer -> [[Integer]]
tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,
productos 2 6 == [[2,3]] productos 3 6 == [[1,2,3]] productos 4 1680 == [[5,6,7,8]] productos 2 5 == []
Comprobar con QuickCheck que si n > 0 y x > 0, entonces
productos n (product [x..x+n-1]) == [[x..x+n-1]]
Usando productos, definir la función
productosDe2y3consecutivos :: [Integer]
cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,
head productosDe2y3consecutivos == 6
Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.
Los horarios de los cursos se pueden representar mediante matrices donde las filas indican los curso, las columnas las horas de clase y el valor correspondiente al curso i y la hora j es verdadero indica que i tiene clase a la hora j.
En Haskell, podemos usar la matrices de la librería Data.Matrix y definir el tipo de los horarios por
type Horario = Matrix Bool
Un ejemplo de horario es
ejHorarios1 :: Horario ejHorarios1 = fromLists [[True, True, False, False], [False, True, True, False], [False, False, True, True]]
en el que el 1º curso tiene clase a la 1ª y 2ª hora, el 2º a la 2ª y a la 3ª y el 3º a la 3ª y a la 4ª.
Definir la función
cursosConflictivos :: Horario -> [Int] -> Bool
tal que (cursosConflictivos h is) se verifica para si los cursos de la lista is hay alguna hora en la que más de uno tiene clase a dicha hora. Por ejemplo,
cursosConflictivos ejHorarios1 [1,2] == True cursosConflictivos ejHorarios1 [1,3] == False
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ó el polinomio n² - 79n + 1601 que 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
Por ejemplo,
generadoresMaximales 4 == ( 3,[(-2,3),(-1,3),(3,3)]) generadoresMaximales 6 == ( 5,[(-1,5),(5,5)]) generadoresMaximales 50 == (43,[(-5,47)]) generadoresMaximales 100 == (48,[(-15,97)]) generadoresMaximales 200 == (53,[(-25,197)]) generadoresMaximales 1650 == (80,[(-79,1601)])
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 ausente2 ([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 exactamente un término de la progresión aritmética que no está en la lista.
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
Definir la función
zigZag :: Int -> Array (Int,Int) Int
tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,
λ> elems (zigZag 3) [0,1,5, 2,4,6, 3,7,8] λ> elems (zigZag 4) [0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15] λ> elems (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] λ> take 15 (elems (zigZag 1000)) [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]
Definir la función
minimaDiferencia :: (Num a, Ord a) => [a] -> a
tal que (minimaDiferencia xs) es el menor valor absoluto de las diferencias entre todos los pares de elementos de xs (que se supone que tiene al menos 2 elementos). Por ejemplo,
minimaDiferencia [1,5,3,19,18,25] == 1 minimaDiferencia [30,5,20,9] == 4 minimaDiferencia [30,5,20,9,5] == 0 minimaDiferencia [1..10^6] == 1
En el primer ejemplo la menor diferencia es 1 y se da entre los elementos 19 y 18; en el 2ª es 4 entre los elementos 5 y 9 y en la 3ª es 0 porque el elemento 5 está repetido.
En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas
41 = 2 + 3 + 5 + 7 + 11 + 13 41 = 11 + 13 + 17
el 240 se puede escribir de tres formas
240 = 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 240 = 53 + 59 + 61 + 67 240 = 113 + 127
y el 311 se puede escribir de 4 formas
311 = 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 311 = 31 + 37 + 41 + 43 + 47 + 53 + 59 311 = 53 + 59 + 61 + 67 + 71 311 = 101 + 103 + 107
Definir la función
sumas :: Integer -> [[Integer]]
tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,
λ> sumas 41 [[2,3,5,7,11,13],[11,13,17]] λ> sumas 240 [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]] λ> sumas 311 [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],[53,59,61,67,71],[101,103,107]] λ> maximum [length (sumas n) | n <- [1..600]] 4
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
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 (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.
Definir la funciones
sumas :: Int -> [[Int]] nSumas :: Int -> Integer
tales que
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 4 == 5 nSumas 123 == 36726740705505779255899443 length (show (nSumas 123456)) == 25801
Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].
Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.
En Haskell, las direcciones y los caminos se pueden definir por
data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion]
Definir la función
reducido :: Camino -> Camino
tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,
reducido [] == [] reducido [N] == [N] reducido [N,O] == [N,O] reducido [N,O,E] == [N] reducido [N,O,E,S] == [] reducido [N,O,S,E] == [N,O,S,E] reducido [S,S,S,N,N,N] == [] reducido [N,S,S,E,O,N] == [] reducido [N,S,S,E,O,N,O] == [O] reducido (take (10^7) (cycle [N,E,O,S])) == []
Nótese que en el penúltimo ejemplo las reducciones son
[N,S,S,E,O,N,O] --> [S,E,O,N,O] --> [S,N,O] --> [O]
Un primo permutable es un número primo tal que todos los números obtenidos permutando sus cifras son primos. Por ejemplo, 337 es un primo permutable ya que 337, 373 y 733 son primos.
Definir las funciones
esPrimoPermutable :: Integer -> Bool primosPermutables :: [Integer]
tales que
esPrimoPermutable 97 == True esPrimoPermutable 337 == True esPrimoPermutable 23 == False
λ> take 20 primosPermutables [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733]
Los números de Lucas son los elementos de la sucesión L(n) definida por
L(0) = 2 L(1) = 1 L(n) = L(n-1) + L(n-2), si n > 1.
Los primeros números de Lucas son
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
Definir las funciones
nLucas :: Integer -> Integer lucas :: [Integer]
tales que
nLucas 5 == 11 nLucas 32 == 4870847 length (show (nLucas (10^5))) == 20899
take 11 lucas == [2,1,3,4,7,11,18,29,47,76,123]
El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que
mn = 1 (mod p)
Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2x3 = 1 (mod 5).
El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.
Definir la función
invMod :: Integer -> Integer -> Maybe Integer
tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,
λ> invMod 2 5 Just 3 λ> invMod 2 6 Nothing λ> [(x,invMod x 5) | x <- [0..4]] [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)] λ> [(x,invMod x 6) | x <- [0..5]] [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)] λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n) True
Definir la función
clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]
tal que (clasesEquivalencia xs r) es la lista de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,
λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3) [[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]] λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0) [[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]] λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y) [[-4,4],[-3,3],[-2,2],[-1,1],[0]]
El factorial generalizado de x respecto de y y z es el producto x(x-z)(x-2z) ... (x-(y-1)z). Por ejemplo, el factorial generalizado de 7 respecto de 3 y 2 es 7x5x3 = 105 y el de 7 respecto de 2 y 3 es 7x4 = 28
Definir la función
factGen :: Integer -> Integer -> Integer -> Integer
tal que (factGen x y z) es el factorial generalizado de x respecto de y y z. Por ejemplo,
factGen 7 3 2 == 105 factGen 7 2 3 == 28
Nota: Se supone que x, y y z son positivos y z < x.
Comprobar con QuickCheck que (factGen x x 1) es el factorial de x.
Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,
6/2 = 3 se representa por (3,[],[]) 1/2 = 0.5 se representa por (0,[5],[]) 1/3 = 0.333333... se representa por (0,[],[3]) 23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])
Su tipo es
type Decimal = (Integer,[Integer],[Integer])
Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es
type Racional = (Integer,Integer)
Definir las funciones
decimal :: Racional -> Decimal racional :: Decimal -> Racional
tales que
decimal (1,4) == (0,[2,5],[]) decimal (1,3) == (0,[],[3]) decimal (23,14) == (1,[6],[4,2,8,5,7,1])
racional (0,[2,5],[]) == (1,4) racional (0,[],[3]) == (1,3) racional (1,[6],[4,2,8,5,7,1]) == (23,14)
Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,
λ> let (_,_,p) = decimal (23,14) in concatMap show p "428571" λ> let (_,_,p) = decimal (1,47) in concatMap show p "0212765957446808510638297872340425531914893617" λ> let (_,_,p) = decimal (1,541) in length (concatMap show p) 540
Comprobar con QuickCheck si las funciones decimal y racional son inversas.
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
Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.
Definir la función
esEspecial :: Integer -> Bool
tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,
esEspecial 1255 == True esEspecial 125 == False
Comprobar con QuickCheck que todo número primo es especial.
Calcular los 5 primeros números especiales que no son primos.
Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato
data Expr = N Int | V Char | Sum Expr Expr | Mul Expr Expr deriving Show
Por ejemplo, (x+3)+(7*y) se representa por
ejExpr :: Expr ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))
Definir la función
valor :: Expr -> Maybe Int
tal que (valor e) es 'Just v' si la expresión e es numérica y v es su valor, o bien 'Nothing' si e no es numérica. Por ejemplo:
valor (Sum (N 7) (N 9)) == Just 16 valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2))) == Just 18
Los vectores se definen usando tablas como sigue:
type Vector a = Array Int a
Un elemento de un vector es un máximo local si no tiene ningún elemento adyacente mayor o igual que él.
Definir la función
posMaxVec :: Ord a => Vector a -> [Int]
tal que (posMaxVec p) devuelve las posiciones del vector p en las que p tiene un máximo local. Por ejemplo,
posMaxVec (listArray (1,6) [3,2,6,7,5,3]) == [1,4] posMaxVec (listArray (1,2) [5,5]) == [] posMaxVec (listArray (1,1) [5]) == [1]
El pasado 11 de marzo se ha publicado el artículo Unexpected biases in the distribution of consecutive primes en el que muestra que los números primos repelen a otros primos que terminan en el mismo dígito.
La lista de los últimos dígitos de los 30 primeros números es
[2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]
Se observa que hay 6 números que su último dígito es un 1 y de sus consecutivos 4 terminan en 3 y 2 terminan en 7.
Definir la función
distribucionUltimos :: Int -> M.Matrix Integer
tal que (distribucionUltimos n) es la matriz cuyo elemento (i,j) indica cuántos de los n primeros números primos terminan en i y su siguiente número primo termina en j. Por ejemplo,
λ> distribucionUltimos 30 ( 0 0 4 0 0 0 2 0 0 ) ( 0 0 1 0 0 0 0 0 0 ) ( 0 0 0 0 1 0 4 0 4 ) ( 0 0 0 0 0 0 0 0 0 ) ( 0 0 0 0 0 0 1 0 0 ) ( 0 0 0 0 0 0 0 0 0 ) ( 4 0 1 0 0 0 0 0 2 ) ( 0 0 0 0 0 0 0 0 0 ) ( 2 0 3 0 0 0 1 0 0 ) λ> distribucionUltimos (10^5) ( 4104 0 7961 0 0 0 8297 0 4605 ) ( 0 0 1 0 0 0 0 0 0 ) ( 5596 0 3604 0 1 0 7419 0 8387 ) ( 0 0 0 0 0 0 0 0 0 ) ( 0 0 0 0 0 0 1 0 0 ) ( 0 0 0 0 0 0 0 0 0 ) ( 6438 0 6928 0 0 0 3627 0 8022 ) ( 0 0 0 0 0 0 0 0 0 ) ( 8830 0 6513 0 0 0 5671 0 3995 )
Nota: Se observa cómo se "repelen" ya que en las filas del 1, 3, 7 y 9 el menor elemento es el de la diagonal.
Definir la función
sumaMaxima :: [Integer] -> Integer
tal que (sumaMaxima xs) es el valor máximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,
sumaMaxima [] == 0 sumaMaxima [2,-2,3,-3,4] == 4 sumaMaxima [-1,-2,-3] == 0 sumaMaxima [2,-1,3,-2,3] == 5 sumaMaxima [1,-1,3,-2,4] == 5 sumaMaxima [2,-1,3,-2,4] == 6 sumaMaxima [1..10^6] == 500000500000
Comprobar con QuickCheck que
sumaMaxima xs == sumaMaxima (reverse xs)
En la siguiente figura, al rotar girando 90 grados en el sentido del reloj la matriz de la izquierda, obtenemos la de la derecha
1 2 3 7 4 1 4 5 6 8 5 2 7 8 9 9 6 3
Definir la función
rota :: Matrix Int -> Matrix Int
tal que (rota p) es la matriz obtenida girando en el sentido del reloj la matriz cuadrada p. Por ejemplo,
λ> rota (fromList 3 3 [1..9]) ( 7 4 1 ) ( 8 5 2 ) ( 9 6 3 ) λ> rota (fromList 3 3 [7,4,1,8,5,2,9,6,3]) ( 9 8 7 ) ( 6 5 4 ) ( 3 2 1 )
Definir la función
seccion :: Eq a => [a] -> [a]
tal que (seccion xs) es el mayor sección inicial de xs que no contiene ningún elemento repetido. Por ejemplo:
seccion [1,2,3,2,4,5] == [1,2,3] seccion "caceres" == "ca" length (seccion ([1..7531] ++ [1..10^9])) == 7531
Definir la sucesión
primosSumaDe2Cuadrados :: [Integer]
cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,
λ> take 20 primosSumaDe2Cuadrados [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181] λ> primosSumaDe2Cuadrados !! (2*10^5) 5803241
En el ejemplo anterior,
Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:
type Matriz = Array (Int,Int) Int
Definir la función
maximaSuma :: Matriz -> Int
tal que (maximaSuma p) es el máximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece sólo a una fila y a una columna. Por ejemplo,
λ> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7]) 17
ya que las selecciones, y sus sumas, de la matriz
|1 2 3| |8 4 9| |5 6 7|
son
[1,4,7] --> 12 [1,9,6] --> 16 [2,8,7] --> 17 [2,9,5] --> 16 [3,8,6] --> 17 [3,4,5] --> 12
Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].
Definir la función
nDivisoresPar :: Integer -> Bool
tal que (nDivisoresPar n) se verifica si n tiene un número par de divisores. Por ejemplo,
nDivisoresPar 12 == True nDivisoresPar 16 == False nDivisoresPar (product [1..2*10^4]) == True
Las sublistas comunes de "1325" y "36572" son "", "3","32", "35", "2" y "5". El máximo de sus longitudes es 2.
Definir la función
maximo :: Eq a => [a] -> [a] -> Int
tal que (maximo xs ys) es el máximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,
maximo "1325" "36572" == 2 maximo [1,4..33] [2,4..33] == 5 maximo [1..10^6] [1..10^6] == 100000
Sea xs una lista y n su longitud. Se dice que xs es casi completa si sus elementos son los números enteros entre 0 y n excepto uno. Por ejemplo, la lista [3,0,1] es casi completa.
Definir la función
ausente :: [Integer] -> Integer
tal que (ausente xs) es el único entero (entre 0 y la longitud de xs) que no pertenece a la lista casi completa xs. Por ejemplo,
ausente [3,0,1] == 2 ausente [1,2,0] == 3 ausente (1+10^7:[0..10^7-1]) == 10000000
Definir la función
menorNoSuma :: [Integer] -> Integer
tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,
menorNoSuma [6,1,2] == 4 menorNoSuma [1,2,3,9] == 7 menorNoSuma [5] == 1 menorNoSuma [1..20] == 211 menorNoSuma [1..10^6] == 500000500001
Comprobar con QuickCheck que para todo n,
menorNoSuma [1..n] == 1 + sum [1..n]
En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(6,3)) [0,0,0, 1,1,0, 1,1,0, 0,0,1, 0,0,1, 1,1,0] ej2 = listArray ((1,1),(6,6)) [1,0,0,0,0,0, 1,0,1,1,1,1, 0,0,0,0,0,0, 1,1,1,0,1,1, 1,1,1,0,1,1, 0,0,0,0,1,1]
Definir la función
numeroDeIslas :: Array (Int,Int) Int -> Int
tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,
numeroDeIslas ej1 == 3 numeroDeIslas ej2 == 4
La sucesión A114258 de la OEIS está formada por los números n tales que el número de ocurrencia de cada dígito d de n en n² es el doble del número de ocurrencia de d en n. Por ejemplo, 72576 es un elemento de A114258 porque tiene un 2, un 5, un 6 y dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5, dos 6 y cuatro 7.
Un número es especial si pertenece a la sucesión A114258.
Definir la sucesión
especiales :: [Integer]
cuyos elementos son los números especiales. Por ejemplo,
take 5 especiales == [72576,406512,415278,494462,603297]
Los primeros términos de la sucesión de Fibonacci son
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Se observa que el 6º término de la sucesión (comenzando a contar en 0) es el número 8.
Definir la función
indiceFib :: Integer -> Maybe Integer
tal que (indiceFib x) es justo el número n si x es el n-ésimo términos de la sucesión de Fibonacci o Nothing en el caso de que x no pertenezca a la sucesión. Por ejemplo,
indiceFib 8 == Just 6 indiceFib 9 == Nothing indiceFib 21 == Just 8 indiceFib 22 == Nothing indiceFib 280571172992510140037611932413038677189525 == Just 200 indiceFib 123456789012345678901234567890123456789012 == Nothing
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) + \cdots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a+nh+\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 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
Definir las funciones
particionesCuadradas :: Integer -> [[Integer]] nParticionesCuadradas :: Integer -> Integer graficaParticionesCuadradas :: Integer -> IO ()
tales que
particionesCuadradas 3 == [[1,1,1]] particionesCuadradas 4 == [[4],[1,1,1,1]] particionesCuadradas 9 == [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]
nParticionesCuadradas 3 == 1 nParticionesCuadradas 4 == 2 nParticionesCuadradas 9 == 4 nParticionesCuadradas 50 == 104 nParticionesCuadradas 100 == 1116 nParticionesCuadradas 200 == 27482
[nParticionesCuadradas k | k <- [0..n]]
Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene
Un número n es automórfico si los últimos dígitos de su cuadrado son los dígitos de n. Por ejemplo, 5, 6, 76 y 890625 son números automórficos ya que 5² = 25, 6² = 36, 76² = 5776 y 890625² = 793212890625.
Definir la sucesión
automorficos :: [Integer]
tal que sus elementos son los números automórficos. Por ejemplo,
λ> take 11 automorficos [1,5,6,25,76,376,625,9376,90625,109376,890625] λ> automorficos !! 30 56259918212890625
Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son
28 = 2² + 2³ + 2⁴ 33 = 3² + 2³ + 2⁴ 47 = 2² + 3³ + 2⁴ 49 = 5² + 2³ + 2⁴
Definir la sucesión
sumas3potencias :: [Integer]
cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,
λ> take 15 sumas3potencias [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138] λ> sumas3potencias !! 234567 8953761
Se observa que todos los primeros números naturales tienen al menos un múltiplo no nulo que está formado solamente por ceros y unos. Por ejemplo, 1x10=10, 2x5=10, 3x37=111, 4x25=100, 5x2=10, 6x185=1110; 7x143=1001; 8X125=1000; 9x12345679=111111111.
Definir la función
multiplosCon1y0 :: Integer -> [Integer]
tal que (multiplosCon1y0 n) es la lista de los múltiplos de n cuyos dígitos son 1 ó 0. Por ejemplo,
take 4 (multiplosCon1y0 3) == [111,1011,1101,1110] take 3 (multiplosCon1y0 23) == [110101,1011011,1101010] head (multiplosCon1y0 1234658) == 110101101101000000110
Comprobar con QuickCheck que todo entero positivo tiene algún múltiplo cuyos dígitos son 1 ó 0.
Dadas dos listas de valores
xs = [x(1), x(2), ..., x(n)] ys = [y(1), y(2), ..., y(n)]
la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde \[ b = \frac{n \sum x_i y_i - \sum x_i \sum y_i}{n \sum x_i^2 - \left( \sum x_i \right)^2} \]
\[ a = \frac{\sum y_i - b \sum x_i}{n} \]
Definir la función
regresionLineal :: [Double] -> [Double] -> (Double,Double)
tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores
ejX, ejY :: [Double] ejX = [5, 7, 10, 12, 16, 20, 23, 27, 19, 14] ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]
se tiene
λ> regresionLineal ejX ejY (5.195045748716805,0.9218924347243919)
Definir el procedimiento
grafica :: [Double] -> [Double] -> IO ()
tal que (grafica xs ys) pinte los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo
El enunciado del problema 652 de Números y algo más es el siguiente
Si factorizamos los factoriales de un número en función de sus divisores primos y sus potencias, ¿Cuál es el menor número n tal que entre los factores primos y los exponentes de estos, n! contiene los dígitos del cero al nueve? Por ejemplo
- 6! = 2⁴x3²x5¹, le faltan los dígitos 0,6,7,8 y 9
- 12! = 2¹⁰x3⁵x5²x7¹x11¹, le faltan los dígitos 4,6,8 y 9
Definir la función
digitosDeFactorizacion :: Integer -> [Integer]
tal que (digitosDeFactorizacion n) es el conjunto de los dígitos que aparecen en la factorización de n. Por ejemplo,
digitosDeFactorizacion (factorial 6) == [1,2,3,4,5] digitosDeFactorizacion (factorial 12) == [0,1,2,3,5,7]
Usando la función anterior, calcular la solución del problema.
Comprobar con QuickCheck que si n es mayor que 100, entonces
digitosDeFactorizacion (factorial n) == [0..9]
Los números de Pentanacci se definen mediante las ecuaciones
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4
Los primeros números de Pentanacci son
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...
Se observa que
Definir la función
nPentanacciImpares :: Integer -> Integer
tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,
nPentanacciImpares 5 == 1 nPentanacciImpares 7 == 2 nPentanacciImpares 10 == 3 nPentanacciImpares 15 == 5 nPentanacciImpares 100 == 33 nPentanacciImpares 1000 == 333 nPentanacciImpares 10000 == 3333 nPentanacciImpares (10^(10^6)) `mod` (10^9) == 333333333 length (show (nPentanacciImpares2 (10^(10^6)))) == 1000000
Los números de Fibonacci se definen mediante las ecuaciones
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1
Los primeros números de Fibonacci son
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4
Los primeros números de Pentanacci son
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...
Definir la sucesión
pentanacci :: [Integer]
cuyos elementos son los números de Pentanacci. Por ejemplo,
λ> take 15 pentanacci [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] λ> (pentanacci !! 70000) `mod` (10^30) 231437922897686901289110700696 λ> length (show (pentanacci !! 70000)) 20550
Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.
Definir la función
diagonal :: [[a]] -> [a]
tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,
diagonal [[3,5,2],[4,7,1],[6,9,0]] == [3,7,0] diagonal [[3,5],[4,7],[6,9]] == [3,7] diagonal [[3,5,2],[4,7,1]] == [3,7] sum (diagonal (replicate 20000 [1..20000])) == 200010000
Definir la función
sumas :: Int -> [Int] -> [Int]
tal que (sumas n xs) es la lista de los números que se pueden obtener como suma de n, o menos, elementos de xs. Por ejemplo,
sumas 0 [2,5] == [0] sumas 1 [2,5] == [0,2,5] sumas 2 [2,5] == [0,2,4,5,7,10] sumas 3 [2,5] == [0,2,4,5,6,7,9,10,12,15] sumas 2 [2,3,5] == [0,2,3,4,5,6,7,8,10] sumas 3 [2,3,5] == [0,2,3,4,5,6,7,8,9,10,11,12,13,15] length (sumas 8 [1..200]) == 1601
Los árboles binarios con datos en los nodos y hojas se definen por
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Eq, Show)
Por ejemplo, el árbol
3
/ \
/ \
4 7
/ \ / \
5 0 0 3
/ \
2 0
se representa por
ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))
Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente
3-0
/ \
/ \
/ \
4-1 7-1
/ \ / \
5-2 0-2 0-2 3-0
/ \
2-3 0-3
Definir la función
anotado :: Arbol a -> Arbol (a,Int)
tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,
λ> anotado ejArbol N (3,0) (N (4,1) (N (5,2) (H (2,3)) (H (0,3))) (H (0,2))) (N (7,1) (H (0,2)) (H (3,2)))
Definir la función
compactada :: [Maybe Int] -> [Int]
tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:
Por ejemplo,
λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6] [2,5,3,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6] [2,1,4,3,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6] [2,1,5,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4] [2,1,4,3,4] λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4] [2,2,4,3,4]
Definir la función
sinEspaciosExtremos :: String -> String
tal que (sinEspaciosExtremos cs) es la cadena obtenida eliminando los espacios blancos de los extremos de la cadena cs. Por ejemplo,
λ> sinEspaciosExtremos " El lunes a las 12:30. " "El lunes a las 12:30."
Sea \( n \) un número natural cuya factorización prima es \[ n = 2^a \cdot p_1^{b_1} \cdots p_n^{b_n} \cdot q_1^{c_1} \cdots q_m^{c_m} \] donde los \( p_i \) son los divisores primos de \( n \) congruentes con \( 3 \) módulo \( 4 \) y los \( q_j \) son los divisores primos de \( n \) congruentes con \( 1 \) módulo \( 4 \). Entonces, el número de formas de descomponer \( n \) como suma de dos cuadrados es \( 0 \), si algún \( b_i \) es impar y es el techo (es decir, el número entero más próximo por exceso) de \[ \frac{(1+c_1) \cdots (1+c_m)}{2} \] en caso contrario. Por ejemplo, el número \( 2^3 \cdot (3^9 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) no se puede descomponer como sumas de dos cuadrados (porque el exponente de \( 3 \) es impar) y el número \( 2^3 \cdot (3^2 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) tiene \( 14 \) descomposiciones como suma de dos cuadrados (porque los exponentes de \( 3 \) y \( 7 \) son pares y el techo de \( \frac{(1+3)(1+6)}{2} \) es \( 14 \)).
Definir la función
nRepresentaciones :: Integer -> Integer
tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,
nRepresentaciones (2^3*3^9*5^3*7^8*13^6) == 0 nRepresentaciones (2^3*3^2*5^3*7^8*13^6) == 14 head [n | n <- [1..], nRepresentaciones n > 8] == 71825
Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad
prop_nRepresentaciones :: Integer -> Property prop_nRepresentaciones n = n > 0 ==> nRepresentaciones2 n == genericLength (representaciones n)
Definir la función
representaciones :: Integer -> [(Integer,Integer)]
tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)]
Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...
Definir la función
factorizacionesH :: Integer -> [[Integer]]
tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]]
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque laa factorización, como para el 441, puede no ser única).
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...
Definir la sucesión
primosH :: [Integer]
tal que sus elementos son los primos de Hilbert. Por ejemplo,
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221
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)
Definir la función
ordPorFrecuencia :: Ord a => [a] -> [a]
tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen menos a los que aparecen más. Por ejemplo,
ordPorFrecuencia "canalDePanama" == "DPcelmnnaaaaa" ordPorFrecuencia "20012016" == "61122000"
El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:
Por ejemplo, el cálculo del mcd(660,420) es
mcd(660,420) = 2*mcd(330,210) [por 1] = 2*2*mcd(165,105) [por 1] = 2*2*mcd(30,105) [por 4] = 2*2*mcd(15,105) [por 2] = 2*2*mcd(15,45) [por 4] = 2*2*mcd(15,15) [por 4] = 2*2*15 [por 8] = 60
Definir la función
mcd :: Integer -> Integer -> Integer
Definir la función
tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,
mcd 660 420 == 60 mcd 3 0 == 3 mcd 0 3 == 3
Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.
Definir la función
agrupa :: (a -> Bool) -> [a] -> [[a]]
tal que (agrupa p xs) es la lista obtenida separando los elementos consecutivos de xs que verifican la propiedad p de los que no la verifican. Por ejemplo,
agrupa odd [1,2,0,4,9,6,4,5,7,2] == [[1],[2,0,4],[9],[6,4],[5,7],[2]] agrupa even [1,2,0,4,9,6,4,5,7,2] == [[],[1],[2,0,4],[9],[6,4],[5,7],[2]] agrupa (> 4) [1,2,0,4,9,6,4,5,7,2] == [[],[1,2,0,4],[9,6],[4],[5,7],[2]] agrupa (< 4) [1,2,0,4,9,6,4,5,7,2] == [[1,2,0],[4,9,6,4,5,7],[2]]
Comprobar con QuickCheck que para cualquier propiedad p y cualquier lista xs, la concatenación de (agrupa p xs) es xs; es decir,
prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool prop_agrupa (Blind p) xs = concat (agrupa1 p xs) == xs
Nota. Usar la librería Test.QuickCheck.Modifiers.
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]
Los árboles binarios con datos en nodos y hojas se definen por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo, el árbol
3
/ \
/ \
4 7
/ \ / \
5 0 0 3
/ \
2 0
se representa por
ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))
Definir la función
sucesores :: Arbol a -> [(a,[a])]
tal que (sucesores t) es la lista de los pares formados por los elementos del árbol t junto con sus sucesores. Por ejemplo,
λ> sucesores ejArbol [(3,[4,7]),(4,[5,0]),(5,[2,0]),(2,[]),(0,[]),(0,[]), (7,[0,3]),(0,[]),(3,[])]
Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,
Definir la función
funciones :: [a] -> [a] -> [[(a,a)]]
tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,
λ> funciones [] [2,4,6] [[]] λ> funciones [3] [2,4,6] [[(3,2)],[(3,4)],[(3,6)]] λ> funciones [1,3] [2,4,6] [[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)], [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]
Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.
Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones +++ OK, passed 100 tests.
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
Definir la lista
serieThueMorse :: [[Integer]]
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
Comprobar con QuickCheck que cada término de la serie de Thue-Morse se obtiene del anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1.
Definir la función
primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]
tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de lista de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,
λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2) [[2,3],[3,5],[5,7],[41,43],[43,47]] λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3) [[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]] λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4) [[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]] λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50 [129197,129209,129221,129223]
Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n. Por ejemplo,
Definir la función
esBelga :: Int -> Int -> Bool
tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,
esBelga 0 18 == True esBelga 1 19 == False esBelga 0 2016 == True [x | x <- [0..30], esBelga 7 x] == [7,10,11,21,27,29] [x | x <- [0..30], esBelga 10 x] == [10,11,20,21,22,24,26] length [n | n <- [1..9000], esBelga 0 n] == 2857
Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.
Definir la función
antiimagen :: (Int -> Int) -> Int -> Maybe Int
tal que (antiimagen f y) es justo el x tal que f(x) = y, si y pertenece a la imagen de la función creciente f, o nada, en caso contrario. Por ejemplo,
antiimagen (^2) 25 == Just 5 antiimagen (^3) 25 == Nothing
Nota. Se supone que f está definida sobre los números naturales.
Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0
Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros
type Matriz = Array (Int,Int) Int
por ejemplo, la matriz de la izquierda de la figura anterior se define por
ej :: Matriz ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Definir la función
relleno :: Matriz -> Matriz
tal que (relleno p) es el relleno de la matriz p. Por ejemplo,
λ> elems (relleno ej) [1,0,0,1,0, 1,0,0,1,0, 1,1,1,1,1, 1,1,1,1,1, 1,0,0,1,0]
Definir la sucesión
primosCon2016 :: [Integer]
tal que sus elementos son los números primos que contienen al 2016. Por ejemplo,
take 5 primosCon2016 == [20161,120163,120167,201611,201623] primosCon2016 !! 111 == 3020167
El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son
Primo Hueco 2 1 3 2 7 4 11 2
El hueco de un número primo p es maximal si es mayor que los huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es
Primo Hueco 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20
Definir la sucesión
primosYhuecosMaximales :: [(Integer,Integer)]
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
λ> take 8 primosYhuecosMaximales [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)] λ> primosYhuecosMaximales !! 20 (2010733,148)
En lógica matemática, un literal es una fórmula atómica o su negación. Se puede definir por el tipo de dato
data Literal = Atom String | Neg Literal deriving (Eq, Show)
Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom "p") y (Neg (Atom "q")), respectivamente.
Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.
Definir la función
tautologia :: [Literal] -> Bool
tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")] True λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")] False λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")] False
La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.
Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.
El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).
Definir la función
nVisibles :: Integer -> Integer
tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,
nVisibles 6 == 23 nVisibles 10 == 63 nVisibles 100 == 6087 nVisibles 1000 == 608383 nVisibles 10000 == 60794971 nVisibles 100000 == 6079301507
En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).
Definir la función
nCambios :: (Num a, Ord a) => [a] -> Int
tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,
nCambios [] == 0 nCambios [6,5,-4,0,-2,-7,0,-8,-1,4] == 2 nCambios [6,5,-4,0, 2,-7,0,-8,-1,4] == 4
La parte libre de cuadrados de un número n es el producto de todos sus divisores primos con exponente impar en la factorización prima de n. Por ejemplo, la parte libre de cuadrados de 360 es 10 ya que 360 = 2³3²5 y 2.5 = 10; además, 360 = 10.6²
La parte cuadrada de un número n es el mayor número cuadrado que divide a n. Por ejemplo, la parte cuadrada de 360 es 6.
Definir las funciones
parteLibre :: Integer -> Integer parteCuadrada :: Integer -> Integer
tales que
parteLibre 360 == 10 parteLibre 1800 == 2 [parteLibre n | n <- [1..14]] == [1,2,3,1,5,6,7,2,1,10,11,3,13,14]
parteCuadrada 360 == 36 parteCuadrada 1800 == 900 [parteCuadrada n | n <- [1..14]] == [1,1,1,4,1,1,1,4,9,1,1,4,1,1]
La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Definir la función
phi :: Integer -> Integer
tal que (phi n) es igual a φ(n). Por ejemplo,
phi 36 == 12 map phi [10..20] == [4,10,4,12,6,8,8,16,6,18,8] phi (3^10^5) `mod` (10^9) == 681333334
Comprobar con QuickCheck que, para todo n > 0, φ(10ⁿ) tiene n dígitos.
Las fórmulas proposicionales construidas con las constantes verdadero (⊤), falso (⊥), las variables proposicionales y las conectivas de negación (¬), conjunción (∧) y disyunción (∨) se pueden definir usando el siguiente tipo de datos
data Prop = Const Bool | Var Char | Neg Prop | Conj Prop Prop | Disj Prop Prop deriving (Eq, Show)
Por ejemplo, la fórmula (A ∧ ⊥) ∨ (⊤ ∧ B) se representa por
Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))
La fórmula dual de una fórmula p es la fórmula obtenida intercambiando en p las ∧ por ∨ y también las ⊤ por ⊥. Por ejemplo, la dual de (A ∧ ⊥) ∨ (⊤ ∧ B) es (A ∨ ⊤) ∧ (⊥ ∨ B)
Definir la función
dual :: Prop -> Prop
tal que (dual p) es la dual de p. Por ejemplo,
λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))) Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))
Definir la función
sucSumaCuadradosDigitos :: Integer -> [Integer]
tal que (sucSumaCuadradosDigitos n) es la sucesión cuyo primer término es n y los restantes se obtienen sumando los cuadrados de los dígitos de su término anterior. Por ejemplo,
λ> take 20 (sucSumaCuadradosDigitos 2016) [2016,41,17,50,25,29,85,89,145,42,20,4,16,37,58,89,145,42,20,4] λ> take 20 (sucSumaCuadradosDigitos 1976) [1976,167,86,100,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] λ> sucSumaCuadradosDigitos 2016 !! (10^8) 145
Definir la función
puntos :: Integer -> [(Integer,Integer)]
tal que (puntos n) es la lista de los puntos (x,y) con coordenadas enteras de la cuadrícula [1..n]x[1..n] (es decir, 1 ≤ x,y ≤ n) tales que |x²-xy-y²| = 1. Por ejemplo,
length (puntos 10) == 5 length (puntos 100) == 10 length (puntos 1000) == 15 length (puntos (10^50000)) == 239249
Un entero positivo n es un número práctico si todos los enteros positivos menores que él se pueden expresar como suma de distintos divisores de n. Por ejemplo, el 12 es un número práctico, ya que todos los enteros positivos menores que 12 se pueden expresar como suma de divisores de 12 (1, 2, 3, 4 y 6) sin usar ningún divisor más de una vez en cada suma:
1 = 1 2 = 2 3 = 3 4 = 4 5 = 2 + 3 6 = 6 7 = 1 + 6 8 = 2 + 6 9 = 3 + 6 10 = 4 + 6 11 = 1 + 4 + 6
En cambio, 14 no es un número práctico ya que 6 no se puede escribir como suma, con sumandos distintos, de divisores de 14.
Definir la función
esPractico :: Integer -> Bool
tal que (esPractico n) se verifica si n es un número práctico. Por ejemplo,
esPractico 12 == True esPractico 14 == False esPractico 2016 == True esPractico 42535295865117307932921825928971026432 == True
Definir las funciones
sumaRedondeos :: Integer -> [Integer] limiteSumaRedondeos :: Integer -> Integer
tales que
redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)
Por ejemplo,
take 5 (sumaRedondeos 1000) == [500,750,875,937,968]
redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...
Por ejemplo,
limiteSumaRedondeos1 2000 == 1999 limiteSumaRedondeos1 2016 == 2016 limiteSumaRedondeos5 (10^308) `mod` (10^10) == 123839487
Definir la función
optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]
tal que (optimos r f xs) es la lista de los elementos de xs donde la función f alcanza sus valores óptimos respecto de la relación r. Por ejemplo,
optimos (<) length ["ab","c","de","f"] == ["c","f"] optimos (>) length ["ab","c","de","f"] == ["ab","de"]
Definir la función
maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]
tal que (maximales r xs) es la lista de los elementos de xs para los que no hay ningún otro elemento de xs mayor según la relación r. Por ejemplo,
maximales (>) [2,3,4,6] == [6] maximales (<) [2,3,4,6] == [2] maximales (\x y -> mod x y == 0) [2,3,4,6] == [4,6] maximales (\x y -> mod y x == 0) [2,3,4,6] == [2,3]
Definir la función
esAnterior :: Eq a => [a] -> a -> a -> Bool
tal que (esAnterior xs y z) se verifica si y ocurre en xs antes que z (que puede no pertenecer a xs). Por ejemplo,
esAnterior [1,3,7,2] 3 2 == True esAnterior [1,3,7,2] 3 1 == False esAnterior [1,3,7,2] 3 5 == True esAnterior [1,3,7,2] 5 3 == False
Definir la función
todosPares :: (a -> b -> c) -> [a] -> [b] -> [c]
tal que (todosPares f xs ys) es el resultado de aplicar la operación f a todos los pares de xs e ys. Por ejemplo,
todosPares (*) [2,3,5] [7,11] == [14,22,21,33,35,55] todosPares (\x y -> x:show y) "ab" [7,5] == ["a7","a5","b7","b5"]
Definir la función
inserta :: [a] -> [[a]] -> [[a]]
tal que (inserta xs yss) es la lista obtenida insertando
y así sucesivamente. Por ejemplo,
inserta [1,2,3] [[4,7],[6],[9,5,8]] == [[1,4,7],[6,2],[9,5,3,8]] inserta [1,2,3] [[4,7],[] ,[9,5,8]] == [[1,4,7],[], [9,5,3,8]] inserta [1,2] [[4,7],[6],[9,5,8]] == [[1,4,7],[6,2],[9,5,8]] inserta [1,2,3] [[4,7],[6]] == [[1,4,7],[6,2]] inserta "tad" ["odo","pra","naa"] == ["todo","para","nada"]
Definir el procedimiento
arbol :: Int -> IO ()
tal que (arbol n) dibuja el árbol de Navidad con una copa de altura n y un tronco de altura la mitad de n. Por ejemplo,
λ> arbol 5 X XXX XXXXX XXXXXXX XXXXXXXXX X X λ> arbol 6 X XXX XXXXX XXXXXXX XXXXXXXXX XXXXXXXXXXX X X X λ> arbol 7 X XXX XXXXX XXXXXXX XXXXXXXXX XXXXXXXXXXX XXXXXXXXXXXXX X X X
Definir la función
siembra :: [Int] -> [Int]
tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,
siembra [4] == [0,1,1,1,1] siembra [0,2] == [0,0,1,1] siembra [4,2] == [0,1,2,2,1]
El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son
siembra [0,4,2] == [0,0,1,2,2,1] siembra [3] == [0,1,1,1] siembra [3,4,2] == [0,1,2,3,2,1] siembra [3,2,1] == [0,1,2,3] sum $ siembra [1..2500] == 3126250
Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.
Nota: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.
Definir la función
productoInfinito :: [Int] -> [Int]
tal que (productoInfinito xs) es la lista infinita que en la posición N tiene el producto de los N primeros elementos de la lista infinita xs. Por ejemplo,
take 5 (productoInfinito [1..]) == [1,2,6,24,120] take 5 (productoInfinito [2,4..]) == [2,8,48,384,3840] take 5 (productoInfinito [1,3..]) == [1,3,15,105,945]
Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.
Una lista hermanada es una lista de números estrictamente positivos en la que cada elemento tiene algún factor primo en común con el siguiente, en caso de que exista, o alguno de los dos es un 1. Por ejemplo,
Definir la función
hermanada :: [Int] -> Bool
tal que (hermanada xs) se verifica si la lista xs es hermanada según la definición anterior. Por ejemplo,
hermanada [2,6,3,9,1,5] == True hermanada [2,3,5] == False hermanada [2,4..1000000] == True
Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.
Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son
4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵, 36 = 6², 49 = 7², 64 = 2⁶, ...
Definir la sucesión
potenciasPerfectas :: [Integer]
cuyos términos son las potencias perfectas. Por ejemplo,
take 10 potenciasPerfectas == [4,8,9,16,25,27,32,36,49,64] potenciasPerfectas !! 100 == 6724
Definir el procedimiento
grafica :: Int -> IO ()
tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja
!Potencias perfectas](/images/Potencias_perfectas.png)
Definir la función
sumaEnPosicion :: [Int] -> [Int] -> Int
tal que (sumaEnPosicion xs ys) es la suma de todos los elementos de xs cuyas posiciones se indican en ys. Por ejemplo,
sumaEnPosicion [1,2,3] [0,2] == 4 sumaEnPosicion [4,6,2] [1,3] == 6 sumaEnPosicion [3,5,1] [0,1] == 8
Definir la función
factorizable :: Integer -> [Integer] -> Bool
tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,
factorizable 1 [2,5,6] == True factorizable 12 [2,5,3] == True factorizable 12 [2,5,6] == True factorizable 12 [7,5,12] == True factorizable 12 [2,3,1] == True factorizable 12 [2,3,0] == True factorizable 24 [12,4,6] == True factorizable 0 [2,3,0] == True factorizable 12 [5,6] == False factorizable 12 [2,5,1] == False factorizable 0 [2,3,5] == False factorizable (product [1..3000]) [1..100000] == True factorizable (1 + product [1..3000]) [1..100000] == False
El año 2016 será un año cúbico porque se puede escribir como la suma de los cubos de 7 números consecutivos; en efecto,
2016 = 3³+ 4³ +...+ 9³
Definir la función
esCubico :: Integer -> Bool
tal que (esCubico x) se verifica si x se puede escribir como la suma de los cubos de 7 números consecutivos. Por ejemplo,
esCubico 2016 == True esCubico 2017 == False esCubico 189005670081900441 == True esCubico 189005670081900442 == False
Un primo con cubo es un número primo p para el que existe algún entero positivo n tal que la expresión n³ + n²p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8³ + 8²×19 = 12³.
Definir la sucesión
primosConCubos :: [Integer]
tal que sus elementos son los primos con cubo. Por ejemplo,
λ> take 6 primosConCubos [7,19,37,61,127,271] λ> length (takeWhile (< 1000000) primosConCubos) 173
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 menor relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S (definida en el ejercicio del lunes): sea
R = [(1,2),(2,5),(5,6)]
la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea
R1 = R ∪ (R ∘ R) = [(1,2),(2,5),(5,6),(1,5),(2,6)]
la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea
R2 = R1 ∪ (R1 ∘ R1) = [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.
Definir la función
clausuraTransitiva :: Eq a => Rel a -> Rel a
tal que (clausuraTransitiva r) es la clausura transitiva de r. Por ejemplo,
λ> clausuraTransitiva [(1,2),(2,5),(5,6)] [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)] λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)] [(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]
Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el
Definir la función
transitiva :: Eq a => [(a,a)] -> Bool
tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,
transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True transitiva [(1,1),(1,3),(3,1),(5,5)] == False
Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por
[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]
La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.
Definir la función
composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]
tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,
λ> composicion [(1,2)] [(2,3),(2,4)] [(1,3),(1,4)] λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] [(1,3),(1,4),(5,3),(5,4)] λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] [(1,3)] λ> composicion [(0,1)] [(2,3)] []
Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.
Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que
22 = 2*11 y 2+2 = 2+(1+1)
y el 4937775 también lo es ya que
4937775 = 3*5*5*65837 y 4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7)
Definir las funciones
esSmith :: Integer -> Bool smith :: [Integer]
tales que
esSmith 22 == True esSmith 29 == False esSmith 2015 == False esSmith 4937775 == True esSmith 4567597056 == True
λ> take 17 smith [4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391] λ> smith !! 2000 62158
Un número de n dígitos es un número de Armstrong si es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo, 371, 8208 y 4210818 son números de Armstrong ya que
371 = 3^3 + 7^3 + 1^3 8208 = 8^4 + 2^4 + 0^4 + 8^4 4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7
Definir las funciones
esArmstrong :: Integer -> Bool armstrong :: [Integer]
tales que
esArmstrong 371 == True esArmstrong 8208 == True esArmstrong 4210818 == True esArmstrong 2015 == False esArmstrong 115132219018763992565095597973971522401 == True esArmstrong 115132219018763992565095597973971522402 == False
λ> take 18 armstrong [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]
Comprobar con QuickCheck que los números mayores que 115132219018763992565095597973971522401 no son números de Armstrong.