{"id":7760,"date":"2022-07-16T12:48:37","date_gmt":"2022-07-16T10:48:37","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7760"},"modified":"2022-07-16T12:48:37","modified_gmt":"2022-07-16T10:48:37","slug":"pfh-la-semana-en-exercitium-15-de-julio-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-15-de-julio-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (15 de julio de 2022)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. N\u00famero de particiones en k subconjuntos<\/a><\/li>\n<li><a href=\"#ej2\">2. Composici\u00f3n de relaciones binarias<\/a><\/li>\n<li><a href=\"#ej3\">3. Transitividad de una relaci\u00f3n<\/a><\/li>\n<li><a href=\"#ej4\">4. Clausura transitiva de una relaci\u00f3n binaria<\/a><\/li>\n<li><a href=\"#ej5\">5. Primos cubanos<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. N\u00famero de particiones en k subconjuntos<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   numeroParticiones :: Int -> Int -> Int\n<\/pre>\n<p>tal que <code>(numeroParticiones n k)<\/code> es el n\u00famero de particiones de conjunto de <code>n<\/code> elementos en <code>k<\/code> subconjuntos disjuntos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   numeroParticiones 3 2    ==  3\n   numeroParticiones 3 3    ==  1\n   numeroParticiones 4 3    ==  6\n   numeroParticiones 4 1    ==  1\n   numeroParticiones 4 4    ==  1\n   numeroParticiones 91 89  ==  8139495\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array (Array, (!), array)\nimport Test.QuickCheck (Positive (Positive), quickCheckWith)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParticiones1 :: Int -> Int -> Int\nnumeroParticiones1 n k =\n  length (particiones1 [1..n] k)\n\nparticiones1 :: [a] -> Int -> [[[a]]]\nparticiones1 [] _     = []\nparticiones1 _  0     = []\nparticiones1 xs 1     = [[xs]]\nparticiones1 (x:xs) k = [[x]:ys | ys <- particiones1 xs (k-1)] ++ \n                        concat [inserta x ys | ys <- particiones1 xs k]\n\n-- (inserta x yss) es la lista obtenida insertando x en cada uno de los\n-- conjuntos de yss. Por ejemplo,\n--    inserta 4 [[3],[2,5]]  ==  [[[4,3],[2,5]],[[3],[4,2,5]]]\ninserta :: a -> [[a]] -> [[[a]]]\ninserta _ []       = []\ninserta x (ys:yss) = ((x:ys):yss) : [ys:zss | zss <- inserta x yss]\n  \n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParticiones2 :: Int -> Int -> Int\nnumeroParticiones2 0 _ = 0\nnumeroParticiones2 _ 0 = 0\nnumeroParticiones2 _ 1 = 1\nnumeroParticiones2 n k = k * numeroParticiones2 (n-1) k +\n                         numeroParticiones2 (n-1) (k-1) \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParticiones3 :: Int -> Int -> Int\nnumeroParticiones3 n k = matrizNumeroParticiones n k ! (n,k)\n\nmatrizNumeroParticiones :: Int -> Int -> Array (Int,Int) Int\nmatrizNumeroParticiones n k = q where\n  q = array ((0,0),(n,k)) [((i,j), f i j) | i <- [0..n], j <- [0..k]]\n  f _ 0 = 0\n  f 0 _ = 0\n  f _ 1 = 1\n  f i j | i == j    = 1\n        | otherwise = j * f (i-1) j + f (i-1) (j-1)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_numeroParticiones :: Positive Int -> Positive Int -> Bool\nprop_numeroParticiones (Positive n) (Positive k) =\n  all (== numeroParticiones1 n k)\n      [numeroParticiones2 n k,\n       numeroParticiones3 n k]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_numeroParticiones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> numeroParticiones1 12 6\n--    1323652\n--    (1.22 secs, 1,152,945,608 bytes)\n--    \u03bb> numeroParticiones2 12 6\n--    1323652\n--    (0.00 secs, 1,283,152 bytes)\n--    \u03bb> numeroParticiones3 12 6\n--    1323652\n--    (0.01 secs, 1,155,864 bytes)\n--\n--    \u03bb> numeroParticiones2 21 19\n--    19285\n--    (2.04 secs, 990,274,976 bytes)\n--    \u03bb> numeroParticiones3 21 19\n--    19285\n--    (0.00 secs, 940,736 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numero_de_particiones_en_k_subconjuntos.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Composici\u00f3n de relaciones binarias<\/h3>\n<p>Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relaci\u00f3n de divisibilidad en el conjunto {1,2,3,6} se representa por<\/p>\n<pre lang=\"text\">\n   [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n<\/pre>\n<p>La composici\u00f3n de dos relaciones binarias R y S en el conjunto A es la relaci\u00f3n binaria formada por los pares (x,y) para los que existe un z tal que (x,z) \u2208 R y (z,y) \u2208 S.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\n<\/pre>\n<p>tal que (composicion r s) es la composici\u00f3n de las relaciones binarias r y s. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> composicion [(1,2)] [(2,3),(2,4)]\n   [(1,3),(1,4)]\n   \u03bb> composicion [(1,2),(5,2)] [(2,3),(2,4)]\n   [(1,3),(1,4),(5,3),(5,4)]\n   \u03bb> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]\n   [(1,3)]\n<\/pre>\n<p><strong>Nota:<\/strong> Se supone que las relaciones binarias son listas sin elementos repetidos.<\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub, sort)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Set.Monad as S (Set, fromList, toList)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion1 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion1 r s =\n  nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion2 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion2 r s =\n  S.toList (composicionS (S.fromList r) (S.fromList s))\n\ncomposicionS :: Ord a => S.Set (a,a) -> S.Set (a,a) -> S.Set (a,a)\ncomposicionS r s =  \n  [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion3 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion3 r s =\n  relAlista (composicionRel (listaArel r) (listaArel s))\n\n-- Una relaci\u00f3n se puede representar por un diccionario donde las claves\n-- son los elementos y los valores son las listas de los elementos con\n-- los que se relaciona.\ntype Rel a = M.Map a [a]\n\n-- (listaArel xys) es la relaci\u00f3n correspondiente a la lista de pares\n-- xys. Por ejemplo.\n--    \u03bb> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n--    fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])]\nlistaArel :: Ord a => [(a,a)] -> Rel a\nlistaArel []          = M.empty\nlistaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys)\n\n-- (composicionRel r s) es la composici\u00f3n de las relaciones r y s. Por\n-- ejemplo,\n--    \u03bb> r = listaArel [(1,2),(5,2)]\n--    \u03bb> s = listaArel [(2,3),(2,4)]\n--    \u03bb> composicionRel r s\n--    fromList [(1,[3,4]),(5,[3,4])]\ncomposicionRel :: Ord a => Rel a -> Rel a -> Rel a\ncomposicionRel r s =\n  M.map f r \n  where f xs = concat (mapMaybe (`M.lookup` s) xs)\n\n-- (relAlista r) es la lista de pares correspondientes a la relaci\u00f3n\n-- r. Por ejemplo,\n--    \u03bb> relAlista (M.fromList [(1,[3,4]),(5,[3,4])])\n--    [(1,3),(1,4),(5,3),(5,4)]\nrelAlista :: Ord a => Rel a -> [(a,a)]\nrelAlista r =\n  nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] \n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_composicion :: [(Int,Int)] -> [(Int,Int)] -> Bool\nprop_composicion r s =\n  all (== sort (composicion1 r' s'))\n      [sort (composicion2 r' s'),\n       sort (composicion3 r' s')]\n  where r' = nub r\n        s' = nub s\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_composicion\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (composicion1 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n--    1999\n--    (1.54 secs, 770,410,352 bytes)\n--    \u03bb> length (composicion2 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n--    1999\n--    (1.66 secs, 1,348,948,096 bytes)\n--    \u03bb> length (composicion3 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]])\n--    1999\n--    (0.07 secs, 6,960,552 bytes)\n--\n--    \u03bb> r100 = [(n,k) | n <- [1..100], k <- [1..n]]\n--    \u03bb> length (composicion1 r100 r100)\n--    5050\n--    (9.91 secs, 4,946,556,944 bytes)\n--    \u03bb> length (composicion2 r100 r100)\n--    5050\n--    (13.59 secs, 15,241,357,536 bytes)\n--    \u03bb> length (composicion3 r100 r100)\n--    5050\n--    (0.35 secs, 52,015,544 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Composicion_de_relaciones_binarias.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Transitividad de una relaci\u00f3n<\/h3>\n<p>Una relaci\u00f3n binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y \u00e9ste \u00faltimo con un tercero, entonces el primero se relaciona con el tercero.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   transitiva :: Ord a => [(a,a)] -> Bool\n<\/pre>\n<p>tal que (transitiva r) se verifica si la relaci\u00f3n r es transitiva.  Por ejemplo,<\/p>\n<pre lang=\"text\">\n   transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True\n   transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False\n   transitiva [(n,n) | n <- [1..10^4]]         ==  True\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (maxSize, quickCheckWith, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva1 :: Ord a => [(a,a)] -> Bool\ntransitiva1 r = \n  and [(x,y) `elem` r | (x,u) <- r, (v,y) <- r, u == v]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva2 :: Ord a => [(a,a)] -> Bool\ntransitiva2 r = \n  all (`elem` r) [(x,y) | (x,u) <- r, (v,y) <- r, u == v]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva3 :: Ord a => [(a,a)] -> Bool\ntransitiva3 r =\n  subconjunto (composicion r r) r\n\n-- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por\n-- ejemplo, \n--    subconjunto [1,3] [3,1,5]  ==  True\n--    subconjunto [3,1,5] [1,3]  ==  False\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto xs ys =\n  all (`elem`ys) xs\n\n-- (composicion r s) es la composici\u00f3n de las relaciones binarias r y\n-- s. Por ejemplo, \n--    \u03bb> composicion [(1,2)] [(2,3),(2,4)]\n--    [(1,3),(1,4)]\n--    \u03bb> composicion [(1,2),(5,2)] [(2,3),(2,4)]\n--    [(1,3),(1,4),(5,3),(5,4)]\n--    \u03bb> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]\n--    [(1,3)]\ncomposicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion r s =\n  nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva4 :: Ord a => [(a,a)] -> Bool\ntransitiva4 r =\n  subconjunto (composicion4 r r) r\n\ncomposicion4 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion4 r s =\n  relAlista (composicionRel (listaArel r) (listaArel s))\n\n-- Una relaci\u00f3n se puede representar por un diccionario donde las claves\n-- son los elementos y los valores son las listas de los elementos con\n-- los que se relaciona.\ntype Rel a = M.Map a [a]\n\n-- (listaArel xys) es la relaci\u00f3n correspondiente a la lista de pares\n-- xys. Por ejemplo.\n--    \u03bb> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n--    fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])]\nlistaArel :: Ord a => [(a,a)] -> Rel a\nlistaArel []          = M.empty\nlistaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys)\n\n-- (composicionRel r s) es la composici\u00f3n de las relaciones r y s. Por\n-- ejemplo,\n--    \u03bb> r = listaArel [(1,2),(5,2)]\n--    \u03bb> s = listaArel [(2,3),(2,4)]\n--    \u03bb> composicionRel r s\n--    fromList [(1,[3,4]),(5,[3,4])]\ncomposicionRel :: Ord a => Rel a -> Rel a -> Rel a\ncomposicionRel r s =\n  M.map f r \n  where f xs = concat (mapMaybe (`M.lookup` s) xs)\n\n-- (relAlista r) es la lista de pares correspondientes a la relaci\u00f3n\n-- r. Por ejemplo,\n--    \u03bb> relAlista (M.fromList [(1,[3,4]),(5,[3,4])])\n--    [(1,3),(1,4),(5,3),(5,4)]\nrelAlista :: Ord a => Rel a -> [(a,a)]\nrelAlista r =\n  nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] \n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_transitiva :: [(Int,Int)] -> Bool\nprop_transitiva r =\n  all (== transitiva1 r)\n      [transitiva2 r,\n       transitiva3 r,\n       transitiva4 r] \n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_transitiva\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> transitiva1 [(n,n) | n <- [1..5*10^3]]\n--    True\n--    (4.27 secs, 1,403,139,032 bytes)\n--    \u03bb> transitiva2 [(n,n) | n <- [1..5*10^3]]\n--    True\n--    (4.24 secs, 1,402,739,056 bytes)\n--    \u03bb> transitiva3 [(n,n) | n <- [1..5*10^3]]\n--    True\n--    (4.41 secs, 1,403,219,880 bytes)\n--    \u03bb> transitiva4 [(n,n) | n <- [1..5*10^3]]\n--    True\n--    (0.46 secs, 16,206,624 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Transitividad_de_una_relacion.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Clausura transitiva de una relaci\u00f3n binaria<\/h3>\n<p>La clausura transitiva de una relaci\u00f3n binaria R es la  relaci\u00f3n transitiva que contiene a R. Se puede calcular<br \/>\nusando la composici\u00f3n de relaciones. Veamos un ejemplo, en el que (R \u2218 S) representa la composici\u00f3n de R y S: sea<\/p>\n<pre lang=\"text\">\n   R = [(1,2),(2,5),(5,6)]\n<\/pre>\n<p>la relaci\u00f3n R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea<\/p>\n<pre lang=\"text\">\n   R1 = R \u222a (R \u2218 R)\n      = [(1,2),(2,5),(5,6),(1,5),(2,6)]\n<\/pre>\n<p>la relaci\u00f3n R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea<\/p>\n<pre lang=\"text\">\n   R2 = R1 \u222a (R1 \u2218 R1)\n      = [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]\n<\/pre>\n<p>La relaci\u00f3n R2 es transitiva y contiene a R. Adem\u00e1s, R2 es la clausura transitiva de R.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   clausuraTransitiva :: Ord a => [(a,a)] -> [(a,a)]   \n<\/pre>\n<p>tal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relaci\u00f3n transitiva que contiene a r. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> clausuraTransitiva [(1,2),(2,5),(5,6)]\n   [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]\n   \u03bb> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]\n   [(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]\n   \u03bb> length (clausuraTransitiva [(n,n+1) | n <- [1..100]])\n   5050\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (union, nub, sort)\nimport Data.Maybe (mapMaybe)\nimport qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nclausuraTransitiva1 :: Ord a => [(a,a)] -> [(a,a)]  \nclausuraTransitiva1 r\n  | transitiva r = r\n  | otherwise    = clausuraTransitiva1 r1\n  where r1 = r `union` composicion r r\n\n-- (transitiva r) se verifica si la relaci\u00f3n r es transitiva. Por\n-- ejemplo, \n--    transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True\n--    transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False\ntransitiva :: Ord a => [(a,a)] -> Bool\ntransitiva r = subconjunto (composicion r r) r\n\n-- (composicion r s) es la composici\u00f3n de las relaciones binarias r y\n-- s. Por ejemplo, \n--    \u03bb> composicion [(1,2)] [(2,3),(2,4)]\n--    [(1,3),(1,4)]\n--    \u03bb> composicion [(1,2),(5,2)] [(2,3),(2,4)]\n--    [(1,3),(1,4),(5,3),(5,4)]\n--    \u03bb> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]\n--    [(1,3)]\ncomposicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] \n\n-- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por\n-- ejemplo, \n--    subconjunto [1,3] [3,1,5]  ==  True\n--    subconjunto [3,1,5] [1,3]  ==  False\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto xs ys = all (`elem` ys) xs\n\n-- 2\u00aa soluci\u00f3n\n-- =============\n\nclausuraTransitiva2 :: Ord a => [(a,a)] -> [(a,a)]  \nclausuraTransitiva2 r\n  | r1 == r   = r\n  | otherwise = clausuraTransitiva2 r1\n  where r1 = r `union` composicion r r\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_clausuraTransitiva :: [(Int,Int)] -> Bool\nprop_clausuraTransitiva r =\n  all (== sort (clausuraTransitiva1 r))\n      [sort (clausuraTransitiva2 r),\n       sort (clausuraTransitiva3 r)]\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_clausuraTransitiva\n--    +++ OK, passed 100 tests.\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nclausuraTransitiva3 :: Ord a => [(a,a)] -> [(a,a)]  \nclausuraTransitiva3 r\n  | transitiva3 r = r\n  | otherwise     = clausuraTransitiva3 r1\n  where r1 = r `union` composicion3 r r\n\ntransitiva3 :: Ord a => [(a,a)] -> Bool\ntransitiva3 r = subconjunto (composicion3 r r) r\n\ncomposicion3 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]\ncomposicion3 r s =\n  relAlista (composicionRel (listaArel r) (listaArel s))\n\n-- Una relaci\u00f3n se puede representar por un diccionario donde las claves\n-- son los elementos y los valores son las listas de los elementos con\n-- los que se relaciona.\ntype Rel a = M.Map a [a]\n\n-- (listaArel xys) es la relaci\u00f3n correspondiente a la lista de pares\n-- xys. Por ejemplo.\n--    \u03bb> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]\n--    fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])]\nlistaArel :: Ord a => [(a,a)] -> Rel a\nlistaArel []          = M.empty\nlistaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys)\n\n-- (composicionRel r s) es la composici\u00f3n de las relaciones r y s. Por\n-- ejemplo,\n--    \u03bb> r = listaArel [(1,2),(5,2)]\n--    \u03bb> s = listaArel [(2,3),(2,4)]\n--    \u03bb> composicionRel r s\n--    fromList [(1,[3,4]),(5,[3,4])]\ncomposicionRel :: Ord a => Rel a -> Rel a -> Rel a\ncomposicionRel r s =\n  M.map f r \n  where f xs = concat (mapMaybe (`M.lookup` s) xs)\n\n-- (relAlista r) es la lista de pares correspondientes a la relaci\u00f3n\n-- r. Por ejemplo,\n--    \u03bb> relAlista (M.fromList [(1,[3,4]),(5,[3,4])])\n--    [(1,3),(1,4),(5,3),(5,4)]\nrelAlista :: Ord a => Rel a -> [(a,a)]\nrelAlista r =\n  nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] \n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (clausuraTransitiva1 [(n,n+1) | n <- [1..60]])\n--    1830\n--    (2.15 secs, 453,533,992 bytes)\n--    \u03bb> length (clausuraTransitiva2 [(n,n+1) | n <- [1..60]])\n--    1830\n--    (2.23 secs, 558,571,904 bytes)\n--    \u03bb> length (clausuraTransitiva3 [(n,n+1) | n <- [1..60]])\n--    1830\n--    (0.25 secs, 207,168,552 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Clausura_transitiva_de_una_relacion_binaria.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Primos cubanos<\/h3>\n<p>Un <a href=\"http:\/\/bit.ly\/1jPy5QZ\">primo cubano<\/a> es un n\u00famero 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\u00b3-4\u00b3.<\/p>\n<p>Definir la sucesi\u00f3n<\/p>\n<pre lang=\"text\">\n   cubanos :: [Integer]\n<\/pre>\n<p>tal que sus elementos son los n\u00fameros cubanos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 15 cubanos\n   [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime)\nimport Test.QuickCheck \n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncubanos1 :: [Integer]\ncubanos1 = filter isPrime (zipWith (-) (tail cubos) cubos) \n\n-- cubos es la lista de los cubos. Por ejemplo,\n--    \u03bb> take 10 cubos\n--    [1,8,27,64,125,216,343,512,729,1000]\ncubos :: [Integer]\ncubos = map (^3) [1..]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncubanos2 :: [Integer]\ncubanos2 = filter isPrime [(x+1)^3 - x^3 | x <- [1..]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncubanos3 :: [Integer]\ncubanos3 = filter isPrime [3*x^2 + 3*x + 1 | x <- [1..]]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_cubanos :: NonNegative Int -> Bool\nprop_cubanos (NonNegative n) =\n  all (== cubanos1 !! n)\n      [cubanos2 !! n,\n       cubanos3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_cubanos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> cubanos1 !! 3000\n--    795066361\n--    (4.21 secs, 16,953,612,192 bytes)\n--    \u03bb> cubanos2 !! 3000\n--    795066361\n--    (4.27 secs, 16,962,597,288 bytes)\n--    \u03bb> cubanos3 !! 3000\n--    795066361\n--    (4.29 secs, 16,956,085,672 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Primos_cubanos.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. N\u00famero de particiones en k subconjuntos 2. Composici\u00f3n de relaciones binarias 3. Transitividad de una relaci\u00f3n 4. Clausura transitiva de una relaci\u00f3n binaria 5. Primos cubanos A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7760"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7760"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7760\/revisions"}],"predecessor-version":[{"id":7761,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7760\/revisions\/7761"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7760"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7760"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7760"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}