{"id":2424,"date":"2016-05-09T08:04:04","date_gmt":"2016-05-09T06:04:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2424"},"modified":"2021-04-25T16:27:08","modified_gmt":"2021-04-25T14:27:08","slug":"conjuntos-de-primos-emparejables-2016","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjuntos-de-primos-emparejables-2016\/","title":{"rendered":"Conjuntos de primos emparejables"},"content":{"rendered":"<p>Un <strong>conjunto de primos emparejables<\/strong> es un conjunto S de n\u00fameros primos tales que al concatenar cualquier par de elementos de S se obtiene un n\u00famero primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   emparejables :: Integer -> Integer -> [[Integer]]\n<\/pre>\n<p>tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   take 5 (emparejables 2   10)  ==  [[3,7]]\n   take 5 (emparejables 3   10)  ==  []\n   take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]\n   take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]\n   take 5 (emparejables 4  100)  ==  []\n   take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes, isPrime)\nimport Data.List (nub, sort)\nimport qualified Data.Set as S\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nemparejables :: Integer -> Integer -> [[Integer]]\nemparejables 0 _ = [[]]\nemparejables n m = \n    nub [sort (x:xs) | x <- takeWhile (<=m) primes,\n                       xs <- xss,\n                       all (x `emparejable`) xs]\n    where xss = emparejables (n-1) m\n\nemparejable :: Integer -> Integer -> Bool\nemparejable x y =\n    isPrime (concatenacion x y) &&\n    isPrime (concatenacion y x)\n\nconcatenacion :: Integer -> Integer -> Integer\nconcatenacion x y =\n    read (show x ++ show y)\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nemparejables2 :: Integer -> Integer -> [[Integer]]\nemparejables2 n m = map reverse (aux n m)\n    where aux 1 m = [[x] | x <- takeWhile (<=m) primes]\n          aux n m = \n              [p:ys | ys@(x:xs) <- xss,\n                      p <- dropWhile (<x) ps,\n                      all (p `emparejable`) ys]\n              where ps  = takeWhile (<=m) primes\n                    xss = aux (n-1) m\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nemparejables3 :: Integer -> Integer -> [[Integer]]\nemparejables3 n m = map S.toList (aux n m)\n    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]\n          aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,\n                                     xs <- xss,\n                                     all (x `emparejable`) xs]\n              where xss = aux (n-1) m\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nemparejables4 :: Integer -> Integer -> [[Integer]]\nemparejables4 n m = map S.toList (aux n m)\n    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]\n          aux n m = \n              [S.insert p ys | ys <- xss,\n                               let (x,xs) = S.deleteFindMax ys,\n                               p <- dropWhile (<x) ps,\n                               all (p `emparejable`) ys]\n              where ps  = takeWhile (<=m) primes\n                    xss = aux (n-1) m\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> head (emparejables 4 1000)\n--    [3,7,109,673]\n--    (20.36 secs, 11,781,891,120 bytes)\n--    \n--    \u03bb> head (emparejables2 4 1000)\n--    [3,7,109,673]\n--    (0.02 secs, 0 bytes)\n--    \n--    \u03bb> head (emparejables3 4 1000)\n--    [3,7,109,673]\n--    (38.04 secs, 21,542,334,024 bytes)\n--    \n--    \u03bb> head (emparejables4 4 1000)\n--    [3,7,109,673]\n--    (0.03 secs, 0 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Un conjunto de primos emparejables es un conjunto S de n\u00fameros primos tales que al concatenar cualquier par de elementos de S se obtiene un n\u00famero primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673,&#8230;<\/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,352,59,351,174,10,24,11,173,95,6,32,33,350,14,34,349],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2424"}],"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=2424"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2424\/revisions"}],"predecessor-version":[{"id":2450,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2424\/revisions\/2450"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2424"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}