# Etiqueta: rem

## Conjunto de divisores

Definir la función

` divisores :: Integer -> [Integer]`

tal que `(divisores x)` es el conjunto de divisores de `x`. Por ejemplo,

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

#### Soluciones

```import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck   -- 1ª solución -- ===========   divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `rem` x == 0]   -- 2ª solución -- ===========   divisores2 :: Integer -> [Integer] divisores2 n = filter ((== 0) . mod n) [1..n]   -- 3ª solución -- ===========   divisores3 :: Integer -> [Integer] divisores3 = nub . sort . map product . subsequences . primeFactors   -- 4ª solución -- ===========   divisores4 :: Integer -> [Integer] divisores4 = sort . map (product . concat) . productoCartesiano . map inits . group . primeFactors   -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss]   -- 5ª solución -- ===========   divisores5 :: Integer -> [Integer] divisores5 = sort . map (product . concat) . sequence . map inits . group . primeFactors   -- Comprobación de equivalencia -- ============================   -- La propiedad es prop_divisores :: Positive Integer -> Bool prop_divisores (Positive n) = all (== divisores1 n) [ divisores2 n , divisores3 n , divisores4 n , divisores5 n ]   -- La comprobación es -- λ> quickCheck prop_divisores -- +++ OK, passed 100 tests.   -- Comparación de la eficiencia -- ============================   -- λ> length (divisores (product [1..11])) -- 540 -- (12.51 secs, 7,983,499,736 bytes) -- λ> length (divisores2 (product [1..11])) -- 540 -- (4.81 secs, 4,790,146,656 bytes) -- λ> length (divisores3 (product [1..11])) -- 540 -- (0.10 secs, 107,339,848 bytes) -- λ> length (divisores4 (product [1..11])) -- 540 -- (0.02 secs, 1,702,616 bytes) -- λ> length (divisores5 (product [1..11])) -- 540 -- (0.02 secs, 1,205,824 bytes) -- -- λ> length (divisores3 (product [1..14])) -- 2592 -- (7.89 secs, 9,378,454,912 bytes) -- λ> length (divisores4 (product [1..14])) -- 2592 -- (0.03 secs, 9,426,528 bytes) -- λ> length (divisores5 (product [1..14])) -- 2592 -- (0.02 secs, 6,636,608 bytes) -- -- λ> length (divisores4 (product [1..25])) -- 340032 -- (1.65 secs, 2,055,558,208 bytes) -- λ> length (divisores5 (product [1..25])) -- 340032 -- (0.88 secs, 1,532,515,304 bytes)```

El código se encuentra en GitHub.

## Código de las alergias

Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:

``` Huevos ........ 1 Cacahuetes .... 2 Mariscos ...... 4 Fresas ........ 8 Tomates ....... 16 Chocolate ..... 32 Polen ......... 64 Gatos ......... 128```

Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).

Los alérgenos se representan mediante el siguiente tipo de dato

``` data Alergeno = Huevos | Cacahuetes | Mariscos | Fresas | Tomates | Chocolate | Polen | Gatos deriving (Enum, Eq, Show, Bounded)```

Definir la función

` alergias :: Int -> [Alergeno]`

tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,

``` λ> alergias 1 [Huevos] λ> alergias 2 [Cacahuetes] λ> alergias 3 [Huevos,Cacahuetes] λ> alergias 5 [Huevos,Mariscos] λ> alergias 255 [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]```

#### Soluciones

[schedule expon=’2022-04-18′ expat=»06:00″]

• Las soluciones se pueden escribir en los comentarios.
• El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

[/schedule]

[schedule on=’2022-04-18′ at=»06:00″]

```import Data.List (subsequences) import Test.QuickCheck   data Alergeno = Huevos | Cacahuetes | Mariscos | Fresas | Tomates | Chocolate | Polen | Gatos deriving (Enum, Eq, Show, Bounded)   -- 1ª solución -- ===========   alergias1 :: Int -> [Alergeno] alergias1 n = [a | (a,c) <- zip alergenos codigos, c `elem` descomposicion n]   -- codigos es la lista de los códigos de los alergenos. codigos :: [Int] codigos = [2^x| x <- [0..7]]   -- (descomposicion n) es la descomposición de n como sumas de potencias -- de 2. Por ejemplo, -- descomposicion 3 == [1,2] -- descomposicion 5 == [1,4] -- descomposicion 248 == [8,16,32,64,128] -- descomposicion 255 == [1,2,4,8,16,32,64,128] descomposicion :: Int -> [Int] descomposicion n = head [xs | xs <- subsequences codigos, sum xs == n]   -- 2ª solución -- ===========   alergias2 :: Int -> [Alergeno] alergias2 = map toEnum . codigosAlergias   -- (codigosAlergias n) es la lista de códigos de alergias -- correspondiente a una puntuación n. Por ejemplo, -- codigosAlergias 1 == [0] -- codigosAlergias 2 == [1] -- codigosAlergias 3 == [0,1] -- codigosAlergias 4 == [2] -- codigosAlergias 5 == [0,2] -- codigosAlergias 6 == [1,2] codigosAlergias :: Int -> [Int] codigosAlergias = aux [0..7] where aux [] _ = [] aux (x:xs) n | odd n = x : aux xs (n `div` 2) | otherwise = aux xs (n `div` 2)   -- 3ª solución -- ===========   alergias3 :: Int -> [Alergeno] alergias3 = map toEnum . codigosAlergias3   codigosAlergias3 :: Int -> [Int] codigosAlergias3 n = [x | (x,y) <- zip [0..7] (int2bin n), y == 1]   -- (int2bin n) es la representación binaria del número n. Por ejemplo, -- int2bin 10 == [0,1,0,1] -- ya que 10 = 0*1 + 1*2 + 0*4 + 1*8 int2bin :: Int -> [Int] int2bin n | n < 2 = [n] | otherwise = n `rem` 2 : int2bin (n `div` 2)   -- 4ª solución -- ===========   alergias4 :: Int -> [Alergeno] alergias4 = map toEnum . codigosAlergias4   codigosAlergias4 :: Int -> [Int] codigosAlergias4 n = map fst (filter ((== 1) . snd) (zip [0..7] (int2bin n)))   -- 5ª solución -- ===========   alergias5 :: Int -> [Alergeno] alergias5 = map (toEnum . fst) . filter ((1 ==) . snd) . zip [0..7] . int2bin   -- 6ª solución -- ===========   alergias6 :: Int -> [Alergeno] alergias6 = aux alergenos where aux [] _ = [] aux (x:xs) n | odd n = x : aux xs (n `div` 2) | otherwise = aux xs (n `div` 2)   -- alergenos es la lista de los alergenos. Por ejemplo. -- take 3 alergenos == [Huevos,Cacahuetes,Mariscos] alergenos :: [Alergeno] alergenos = [minBound..maxBound]   -- Comprobación de equivalencia -- ============================   -- La propiedad es prop_alergias :: Property prop_alergias = forAll (arbitrary `suchThat` esValido) \$ \n -> all (== alergias1 n) [alergias2 n, alergias3 n, alergias4 n, alergias5 n, alergias6 n] where esValido x = 1 <= x && x <= 255   -- La comprobación es -- λ> quickCheck prop_alergias -- +++ OK, passed 100 tests.   -- Comparación de eficiencia -- =========================   -- La comparación es -- λ> last (map alergias1 [1..255]) -- [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos] -- (0.02 secs, 1,657,912 bytes) -- λ> last (map alergias2 [1..255]) -- [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos] -- (0.01 secs, 597,080 bytes) -- λ> last (map alergias3 [1..255]) -- [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos] -- (0.01 secs, 597,640 bytes) -- λ> last (map alergias4 [1..255]) -- [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos] -- (0.01 secs, 598,152 bytes) -- λ> last (map alergias5 [1..255]) -- [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos] -- (0.01 secs, 596,888 bytes)```

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Alergias.hs).

La elaboración de las soluciones se describe en el siguiente vídeo

#### Nuevas soluciones

• En los comentarios se pueden escribir nuevas soluciones.
• El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

[/schedule]

El complemento de un número positivo x se calcula por el siguiente procedimiento:

• si x es mayor que 9, se toma cada dígito por su valor posicional y se resta del mayor los otro dígitos. Por ejemplo, el complemento de 1448 es 1000 – 400 – 40 – 8 = 552. Para
• si x es menor que 10, su complemento es x.

Definir las funciones

``` cadena :: Integer -> [Integer] conCadena :: Int -> [Integer]```

tales que

• (cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,
``` cadena 8 == [] cadena 7 == [7] cadena 13 == [13,7] cadena 643 == [643,557,443] cadena 18127 == [18127,1873,127,73,67,53,47] cadena 18181213 == [18181213,1818787,181213,18787,1213,787,613,587]```
• (conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,
``` take 6 (conCadena 3) == [23,31,61,67,103,307] [head (conCadena n) | n <- [4..8]] == [37,43,157,18127,181873]```

#### Soluciones

```  import Data.Numbers.Primes   -- (complemento x) es le complemento de x. Por ejemplo, -- complemento 1448 == 552 -- complemento 639 == 561 -- complemento 7 == 7 complemento :: Integer -> Integer complemento x = (div x c)*c - (rem x c) where c = 10^(length (show x) - 1)   cadena :: Integer -> [Integer] cadena x | x < 10 && isPrime x = [x] | otherwise = takeWhile isPrime (iterate f x) where f x | x < 10 && isPrime x = 0 | otherwise = complemento x   conCadena :: Int -> [Integer] conCadena n = [y | y <- primes, length (cadena y) == n]```

## Pares definidos por su MCD y su MCM

Definir las siguientes funciones

``` pares :: Integer -> Integer -> [(Integer,Integer)] nPares :: Integer -> Integer -> Integer```

tales que

• (pares a b) es la lista de los pares de números enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
``` pares 3 3 == [(3,3)] pares 4 12 == [(4,12),(12,4)] pares 2 12 == [(2,12),(4,6),(6,4),(12,2)] pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)] pares 2 7 == [] pares 12 3 == [] length (pares 3 (product [3,5..91])) == 8388608```
• (nPares a b) es el número de pares de enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
``` nPares 3 3 == 1 nPares 4 12 == 2 nPares 2 12 == 4 nPares 2 60 == 8 nPares 2 7 == 0 nPares 12 3 == 0 nPares 3 (product [3..3*10^4]) `mod` (10^12) == 477999992832 length (show (nPares 3 (product [3..3*10^4]))) == 977```

#### Soluciones

```import Data.Numbers.Primes (primeFactors) import Data.List (genericLength, group, nub, sort, subsequences) import Test.QuickCheck   -- 1ª definición de pares -- ======================   pares1 :: Integer -> Integer -> [(Integer,Integer)] pares1 a b = [(x,y) | x <- [1..b] , y <- [1..b] , gcd x y == a , lcm x y == b]   -- 2ª definición de pares -- ======================   pares2 :: Integer -> Integer -> [(Integer,Integer)] pares2 a b = [(x,y) | x <- [a,a+a..b] , y <- [a,a+a..b] , gcd x y == a , lcm x y == b]   -- Comparación de eficiencia -- λ> length (pares1 3 (product [3,5..11])) -- 16 -- (95.12 secs, 86,534,165,528 bytes) -- λ> length (pares2 3 (product [3,5..11])) -- 16 -- (15.80 secs, 14,808,762,128 bytes)   -- 3ª definición de pares -- ======================   pares3 :: Integer -> Integer -> [(Integer,Integer)] pares3 a b = [(x,y) | x <- [a,a+a..b] , c `rem` x == 0 , let y = c `div` x , gcd x y == a ] where c = a * b   -- Comparacioń de eficiencia -- λ> length (pares2 3 (product [3,5..11])) -- 16 -- (15.80 secs, 14,808,762,128 bytes) -- λ> length (pares3 3 (product [3,5..11])) -- 16 -- (0.01 secs, 878,104 bytes)   -- 4ª definición de pares -- ======================   -- Para la cuarta definición de pares se observa la relación con los -- factores primos -- λ> [(primeFactors x, primeFactors y) | (x,y) <- pares1 2 12] -- [([2],[2,2,3]),([2,2],[2,3]),([2,3],[2,2]),([2,2,3],[2])] -- λ> [primeFactors x | (x,y) <- pares1 2 12] -- [[2],[2,2],[2,3],[2,2,3]] -- λ> [primeFactors x | (x,y) <- pares1 2 60] -- [[2],[2,2],[2,3],[2,5],[2,2,3],[2,2,5],[2,3,5],[2,2,3,5]] -- λ> [primeFactors x | (x,y) <- pares1 6 60] -- [[2,3],[2,2,3],[2,3,5],[2,2,3,5]] -- λ> [primeFactors x | (x,y) <- pares1 2 24] -- [[2],[2,3],[2,2,2],[2,2,2,3]] -- Se observa que cada pares se obtiene de uno de los subconjuntos de los -- divisores primos de b/a. Por ejemplo, -- λ> (a,b) = (2,24) -- λ> b `div` a -- 12 -- λ> primeFactors it -- [2,2,3] -- λ> group it -- [[2,2],[3]] -- λ> subsequences it -- [[],[[2,2]],[[3]],[[2,2],[3]]] -- λ> map concat it -- [[],[2,2],[3],[2,2,3]] -- λ> map product it -- [1,4,3,12] -- λ> [(a * x, b `div` x) | x <- it] -- [(2,24),(8,6),(6,8),(24,2)] -- A partir de la observación se construye la siguiente definición   pares4 :: Integer -> Integer -> [(Integer,Integer)] pares4 a b | b `mod` a /= 0 = [] | otherwise = [(a * x, b `div` x) | x <- map (product . concat) ((subsequences . group . primeFactors) (b `div` a))]   -- Nota. La función pares4 calcula el mismo conjunto que las anteriores, -- pero no necesariamente en el mismo orden. Por ejemplo, -- λ> pares3 2 60 -- [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)] -- λ> pares4 2 60 -- [(2,60),(4,30),(6,20),(12,10),(10,12),(20,6),(30,4),(60,2)] -- λ> pares3 2 60 == sort (pares4 2 60) -- True   -- Comparacioń de eficiencia -- λ> length (pares3 3 (product [3,5..17])) -- 64 -- (4.44 secs, 2,389,486,440 bytes) -- λ> length (pares4 3 (product [3,5..17])) -- 64 -- (0.00 secs, 177,704 bytes)   -- Propiedades de equivalencia de pares -- ====================================   prop_pares :: Integer -> Integer -> Property prop_pares a b = a > 0 && b > 0 ==> all (== pares1 a b) [sort (f a b) | f <- [ pares2 , pares3 , pares4 ]]   prop_pares2 :: Integer -> Integer -> Property prop_pares2 a b = a > 0 && b > 0 ==> all (== pares1 a (a * b)) [sort (f a (a * b)) | f <- [ pares2 , pares3 , pares4 ]]   -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares -- +++ OK, passed 100 tests. -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares -- +++ OK, passed 100 tests. -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_pares2 -- +++ OK, passed 100 tests.   -- 1ª definición de nPares -- =======================   nPares1 :: Integer -> Integer -> Integer nPares1 a b = genericLength (pares4 a b)   -- 2ª definición de nPares -- =======================   nPares2 :: Integer -> Integer -> Integer nPares2 a b = 2^(length (nub (primeFactors (b `div` a))))   -- Comparación de eficiencia -- λ> nPares1 3 (product [3,5..91]) -- 8388608 -- (4.68 secs, 4,178,295,920 bytes) -- λ> nPares2 3 (product [3,5..91]) -- 8388608 -- (0.00 secs, 234,688 bytes)   -- Propiedad de equivalencia de nPares -- ===================================   prop_nPares :: Integer -> Integer -> Property prop_nPares a b = a > 0 && b > 0 ==> nPares1 a (a * b) == nPares2 a (a * b)   -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_nPares -- +++ OK, passed 100 tests.```

#### Pensamiento

Largo es el camino de la enseñanza por medio de teorías; breve y eficaz por medio de ejemplos. ~ Séneca

## Múltiplos con ceros y unos

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, 1×10=10, 2×5=10, 3×37=111, 4×25=100, 5×2=10, 6×185=1110; 7×143=1001; 8X125=1000; 9×12345679=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.

#### Soluciones

```import Test.QuickCheck   -- 1ª definición -- =============   multiplosCon1y0 :: Integer -> [Integer] multiplosCon1y0 n = [x | x <- multiplos n , todos1y0 x]   -- (multiplos n) es la lista de los múltiplos de n. Por ejemplo, -- take 12 (multiplos 5) == [5,10,15,20,25,30,35,40,45,50,55,60] multiplos :: Integer -> [Integer] multiplos n = [n,2*n..]   -- (todos1y0 n) se verifica si todos los dígitos de n son el 1 o el -- 0. Por ejmplo, -- todos1y0 1101110 == True -- todos1y0 1102110 == False todos1y0 :: Integer -> Bool todos1y0 n = all (`elem` "01") (show n)   -- 2ª definición -- =============   multiplosCon1y0b :: Integer -> [Integer] multiplosCon1y0b n = [x | x <- numerosCon1y0 , x `rem` n == 0]   -- numerosCon1y0 es la lista de los números cuyos dígitos son 1 ó 0. Por -- ejemplo, -- ghci> take 15 numerosCon1y0 -- [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111] numerosCon1y0 :: [Integer] numerosCon1y0 = 1 : concat [[10*x,10*x+1] | x <- numerosCon1y0]   -- Comparación de eficiencia -- =========================   -- λ> head (multiplosCon1y0 9) -- 111111111 -- (7.70 secs, 10,853,320,456 bytes) -- λ> head (multiplosCon1y0b 9) -- 111111111 -- (0.01 secs, 167,992 bytes)   -- Comprobación de la propiedad -- ============================   -- La propiedad es prop_existe_multiplosCon1y0 :: Integer -> Property prop_existe_multiplosCon1y0 n = n > 0 ==> (not . null) (multiplosCon1y0b n)   -- La comprobación es -- λ> quickCheck prop_existe_multiplosCon1y0 -- +++ OK, passed 100 tests.```

#### Pensamiento

Huye del triste amor, amor pacato,
sin peligro, sin venda ni aventura,
que espera del amor prenda segura,
porque en amor locura es lo sensato.