Los n\u00fameros compuestos por un conjunto de primos son los n\u00fameros cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros n\u00fameros compuestos por [2,5,7] son<\/p>\n
\n 1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...\n<\/pre>\nEl 28 es compuesto ya que sus divisores primos son 2 y 7 que est\u00e1n en [2,5,7].<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n compuestos :: [Integer] -> [Integer]\n<\/pre>\ntal que (compuesto ps) es la lista de los n\u00fameros compuestos por el conjunto de primos ps. Por ejemplo,<\/p>\n
\n \u03bb> take 20 (compuestos [2,5,7])\n [1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]\n \u03bb> take 20 (compuestos [2,5])\n [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]\n \u03bb> take 20 (compuestos [2,3,5])\n [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]\n \u03bb> take 20 (compuestos [3,5,7,11,13])\n [1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]\n \u03bb> take 15 (compuestos [2])\n [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]\n \u03bb> compuestos [2,7] !! (10^4)\n 57399514149595471961908157955229677377312712667508119466382354072731648\n \u03bb> compuestos [2,3,5] !! (10^5)\n 290237644800000000000000000000000000000\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Numbers.Primes (primeFactors)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos1 :: [Integer] -> [Integer]\ncompuestos1 ps =\n [n | n <- [1..], esCompuesto ps n]\n\n-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen\n-- a ps. Por ejemplo, \n-- esCompuesto [2,3,7] 28 == True\n-- esCompuesto [2,3,7] 140 == False\n-- esCompuesto [2,3,5,7] 140 == True\nesCompuesto :: [Integer] -> Integer -> Bool\nesCompuesto ps n =\n subconjunto (primeFactors n) ps\n\n-- (subconjunto xs ys) se verifica si todos los elementos de xs\n-- pertenecen a ys. Por ejemplo, \n-- subconjunto [2,7,2] [7,5,2] == True\n-- subconjunto [2,7,3] [7,5,2] == False\nsubconjunto :: Eq a => [a] -> [a] -> Bool\nsubconjunto xs ys =\n all (`elem` ys) xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos2 :: [Integer] -> [Integer]\ncompuestos2 ps =\n 1 : mezclaTodas (combinaciones ps)\n\n-- (combinaciones ps) es la lista de los productos de cada elemento de\n-- ps por los n\u00fameros compuestos con ps. Por ejemplo,\n-- \u03bb> take 8 (compuestos4 [2,5,7])\n-- [1,2,4,5,7,8,10,14]\n-- \u03bb> map (take 6) (combinaciones [2,5,7])\n-- [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]\ncombinaciones :: [Integer] -> [[Integer]]\ncombinaciones ps =\n [[p * q | q <- compuestos2 ps] | p <- ps]\n\n-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como\n-- sus elementos son listas infinitas ordenadas. Por ejemplo, \n-- \u03bb> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])\n-- [2,3,4,5,6,7,8,9,10,11]\n-- \u03bb> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])\n-- [2,4,6,8,9,10,12,14,16,18]\nmezclaTodas :: [[Integer]] -> [Integer]\nmezclaTodas = foldr1 xmezcla\n where xmezcla (x:xs) ys = x : mezcla xs ys\n\n-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista\n-- ordenadas xs e ys. Por ejemplo, \nmezcla :: [Integer] -> [Integer] -> [Integer]\nmezcla [] ys = ys\nmezcla xs [] = xs\nmezcla us@(x:xs) vs@(y:ys) | x == y = x : mezcla xs ys\n | x < y = x : mezcla xs vs\n | otherwise = y : mezcla us ys\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos3 :: [Integer] -> [Integer]\ncompuestos3 [] = [1]\ncompuestos3 (p:ps) =\n mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos4 :: [Integer] -> [Integer]\ncompuestos4 ps = foldl aux xs (tail ps)\n where p = head ps\n xs = [p^k | k <- [0..]]\n aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos5 :: [Integer] -> [Integer]\ncompuestos5 = foldl aux [1] \n where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\ncompuestos6 :: [Integer] -> [Integer]\ncompuestos6 xs = aux\n where aux = 1 : mezclas xs aux\n mezclas [] _ = []\n mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> compuestos1 [2,3,5] !! 300\n-- 84375\n-- (5.85 secs, 2,961,101,088 bytes)\n-- \u03bb> compuestos2 [2,3,5] !! 300\n-- 84375\n-- (3.54 secs, 311,137,952 bytes)\n-- \u03bb> compuestos2 [2,3,5] !! 400\n-- 312500\n-- (13.01 secs, 1,229,801,184 bytes)\n-- \u03bb> compuestos3 [2,3,5] !! 400\n-- 312500\n-- (0.02 secs, 2,066,152 bytes)\n-- \u03bb> compuestos3 [2,3,5] !! 20000\n-- 15441834907098675000000\n-- (1.57 secs, 203,061,864 bytes)\n-- \u03bb> compuestos4 [2,3,5] !! 20000\n-- 15441834907098675000000\n-- (0.40 secs, 53,335,080 bytes)\n-- \u03bb> compuestos4 [2,3,5] !! 50000\n-- 2379528690747474604574166220800\n-- (1.25 secs, 170,058,496 bytes)\n-- \u03bb> compuestos5 [2,3,5] !! 50000\n-- 2379528690747474604574166220800\n-- (1.26 secs, 170,104,648 bytes)\n-- \u03bb> compuestos6 [2,3,5] !! 50000\n-- 2379528690747474604574166220800\n-- (0.26 secs, 40,490,280 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Los n\u00fameros compuestos por un conjunto de primos son los n\u00fameros cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros n\u00fameros compuestos por [2,5,7] son 1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,… El 28 es compuesto ya que sus divisores primos son 2 y 7 que est\u00e1n en [2,5,7]. Definir la funci\u00f3n compuestos :: [Integer] -> [Integer] tal que (compuesto…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[7],"tags":[41,8,26,185,243,71,415,10,11,247,6,45],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3992"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=3992"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3992\/revisions"}],"predecessor-version":[{"id":4024,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3992\/revisions\/4024"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3992"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3992"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3992"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}