{"id":5980,"date":"2021-01-15T06:00:17","date_gmt":"2021-01-15T04:00:17","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5980"},"modified":"2021-01-22T14:20:32","modified_gmt":"2021-01-22T12:20:32","slug":"numeros-compuestos-persistentes","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-compuestos-persistentes\/","title":{"rendered":"N\u00fameros compuestos persistentes"},"content":{"rendered":"<p>Un <a href=\"https:\/\/bit.ly\/38rsyNs\">n\u00famero compuesto persistente<\/a> es un n\u00famero compuesto que no se puede transformar en un n\u00famero primo cambiando s\u00f3lo uno de sus d\u00edgitos. Por ejemplo,<\/p>\n<ul>\n<li>20 no es un compuesto persistente porque cambiando su \u00faltimo d\u00edgito por un 3 se transforma en 23 que es primo.<\/li>\n<li>25 no es un compuesto persistente porque cambiando su primer d\u00edgito por un 0 se transforma en 5 que es primo.<\/li>\n<li>200 es un compuesto persistente ya que al cambiar su \u00fatimo d\u00edgito por un impar se obtienen los n\u00fameros 201, 203, 207, 205 y 209 que no son primos y todos sus dem\u00e1s transformados son pares y, por tanto, tampoco son primos.<\/li>\n<\/ul>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esCompuestoPersistente :: Integer -> Bool\n   compuestosPersistentes :: [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esCompuestoPersistente n) se verifica si n es un n\u00famero compuesto persistente. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     esCompuestoPersistente 20    ==  False\n     esCompuestoPersistente 200   ==  True\n     esCompuestoPersistente 2021  ==  False\n<\/pre>\n<ul>\n<li>compuestosPersistentes es la lista de los n\u00fameros compuestos persistentes. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 10 compuestoPersistentes\n     [200,204,206,208,320,322,324,325,326,328]\n<\/pre>\n<p>Comprobar con QuickCheck que todos los n\u00fameros de la forma 510+2310*k son n\u00fameros compuestos persistentes.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primes)\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesCompuestoPersistente :: Integer -> Bool\nesCompuestoPersistente n =\n  esCompuesto n && all (not . isPrime) (transformados n)\n\n-- (eCompuesto n) se verifica si n es un n\u00famero compuesto. Por ejemplo,\n--    esCompuesto 15  ==  True\n--    esCompuesto 16  ==  True\n--    esCompuesto 17  ==  False\nesCompuesto :: Integer -> Bool\nesCompuesto n =  n > 1 && not (isPrime n)\n\n-- (transformados n) es la lista delos n\u00fameros obtenidos modificando uno\n-- de los d\u00edgitos de n. Por ejemplo,\n--    \u03bb> transformados 27\n--    [7,17,37,47,57,67,77,87,97,20,21,22,23,24,25,26,28,29]\ntransformados :: Integer -> [Integer]\ntransformados n = map read (aux (show n))\n  where aux []     = []\n        aux [x]    = [[y] | y <- ['0'..'9'], y \/= x]\n        aux (x:xs) = [y:xs | y <- ['0'..'9'], y \/= x] ++\n                     [x:ys | ys <- aux xs]\n\ncompuestosPersistentes :: [Integer]\ncompuestosPersistentes = filter esCompuestoPersistente [1..]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesCompuestoPersistente2 :: Integer -> Bool\nesCompuestoPersistente2 n =\n  not (any (esTransformadoDe n) (takeWhile (<=10^m-1) primes))\n  where m = length (show n)\n\n-- (esTransformadoDe m n) se verifica si n se puede obtener modificando uno\n-- de los d\u00edgitos de n. Por ejemplo,\n--    esTransformadoDe 27 47  ==  True\n--    esTransformadoDe 27 25  ==  True\n--    esTransformadoDe 27 45  ==  False\n--    esTransformadoDe 27 7   ==  True\n--    esTransformadoDe 27 2   ==  False\nesTransformadoDe :: Integer -> Integer -> Bool\nesTransformadoDe m n =\n  1 == length (filter (==False) (zipWith (==) xs zs))\n  where xs = show m\n        ys = show n\n        zs = replicate (length xs - length ys) '0' ++ ys\n\ncompuestosPersistentes2 :: [Integer]\ncompuestosPersistentes2 = filter esCompuestoPersistente2 [1..]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesCompuestoPersistente3 :: Integer -> Bool\nesCompuestoPersistente3 n =\n  null (primosTransformados n)\n\n-- (primosTransformados n) es la lista de los n\u00fameros primos que se\n-- puede obtener modificando uno de los d\u00edgitos de n. Por ejemplo,\n--    primosTransformados 27   ==  [17,23,29,37,47,67,97,7]\n--    primosTransformados 26   ==  [23,29]\n--    primosTransformados 200  ==  []\n--    primosTransformados 202  ==  [2]\nprimosTransformados :: Integer -> [Integer]\nprimosTransformados n =\n  [x | x <- primosNdigitos p, difierenEnUnaPosicion n x] ++\n  [x | x <- [read ('0' : tail ns)], isPrime x]\n  where ns = show n\n        p  = length ns\n\n-- (difierenEnUnaPosicion m n) se verifica si los n\u00fameros m y n difieren\n-- en una posici\u00f3n (suponiendo que m y n tienen el mismo n\u00famero de\n-- d\u00edgitos). Por ejemplo,\n--    difierenEnUnaPosicion 325 375  ==  True\n--    difierenEnUnaPosicion 325 357  ==  False\ndifierenEnUnaPosicion :: Integer -> Integer -> Bool\ndifierenEnUnaPosicion m n =\n  1 == length (filter (==False) (zipWith (==) (show m) (show n)))\n\n-- (primosNdigitos n) es la lista de los primos con n d\u00edgitos. Por\n-- ejemplo,\n--    \u03bb> primosNdigitos 2\n--    [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]\nprimosNdigitos :: Int -> [Integer]\nprimosNdigitos n = takeWhile (<=10^n-1) (dropWhile (<=10^(n-1)) primes)\n\ncompuestosPersistentes3 :: [Integer]\ncompuestosPersistentes3 = filter esCompuestoPersistente3 [1..]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nesCompuestoPersistente4 :: Integer -> Bool\nesCompuestoPersistente4 n =\n  null (primosTransformados2 n)\n\n-- (primosTransformados2 n) es la lista de los n\u00fameros primos que se\n-- puede obtener modificando uno de los d\u00edgitos de n. Por ejemplo,\n--    primosTransformados2 27   ==  [17,23,29,37,47,67,97,7]\n--    primosTransformados2 26   ==  [23,29]\n--    primosTransformados2 200  ==  []\n--    primosTransformados2 202  ==  [2]\nprimosTransformados2 :: Integer -> [Integer]\nprimosTransformados2 n =\n  [x | x <- primosEntre (menorTransformado n) (mayorTransformado n)\n     , difierenEnUnaPosicion n x] ++\n  [x | x <- [read ('0' : tail ns)], isPrime x]\n  where ns = show n\n        p  = length ns\n\n-- (primosEntre x y) lista de n\u00fameros prios mayores o iguales que x y\n-- menores o iguales que y. Por ejemplo,\n--    primosEntre 11 41  ==  [11,13,17,19,23,29,31,37,41]\nprimosEntre ::Integer -> Integer -> [Integer]\nprimosEntre x y = takeWhile (<= y) (dropWhile (< x) primes)\n\n-- (menorTransformado x) es el menor n\u00famero, con la misma cantidad de\n-- d\u00edgitos que x, que se puede obtener modificando uno de los d\u00edgitos de\n-- n. Por ejemplo,\n--    menorTransformado 375   ==  175\n--    menorTransformado 14    ==  11\n--    menorTransformado 4     ==  1\n--    menorTransformado 1145  ==  1115\nmenorTransformado :: Integer -> Integer\nmenorTransformado x\n  | x <= 9    = 1\n  | y > '1'   = read ('1' : ys)\n  | otherwise = read ('1' : show (menorTransformado (read ys)))\n  where (y:ys) = show x\n\n-- (mayorTransformado x) es el mayor n\u00famero, con la misma cantidad de\n-- d\u00edgitos que x, que se puede obtener modificando uno de los d\u00edgitos de\n-- n. Por ejemplo,\n--    mayorTransformado 375   ==  975\n--    mayorTransformado 93    ==  99\n--    mayorTransformado 4     ==  9\n--    mayorTransformado 9945  ==  9995\nmayorTransformado :: Integer -> Integer\nmayorTransformado x\n  | x <= 9    = 9\n  | y < '9'   = read ('9' : ys)\n  | otherwise = read ('9' : show (mayorTransformado (read ys)))\n  where (y:ys) = show x\n\ncompuestosPersistentes4 :: [Integer]\ncompuestosPersistentes4 = filter esCompuestoPersistente4 [1..]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> compuestosPersistentes !! 1000\n--    8180\n--    (0.54 secs, 1,577,628,232 bytes)\n--    \u03bb> compuestosPersistentes2 !! 1000\n--    8180\n--    (10.13 secs, 15,883,929,392 bytes)\n--    \u03bb> compuestosPersistentes3 !! 1000\n--    8180\n--    (7.09 secs, 14,165,470,304 bytes)\n--    \u03bb> compuestosPersistentes4 !! 1000\n--    8180\n--    (6.54 secs, 13,332,608,480 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_compuestosPersistentes :: Integer -> Property\nprop_compuestosPersistentes k =\n  k > 0 ==> esCompuestoPersistente (510 + 2310 * k)\n\n-- La comprobaci\u00f3n de la propiedad es\n--    \u03bb> quickCheck prop_compuestosPersistentes\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Un n\u00famero compuesto persistente es un n\u00famero compuesto que no se puede transformar en un n\u00famero primo cambiando s\u00f3lo uno de sus d\u00edgitos. Por ejemplo, 20 no es un compuesto persistente porque cambiando su \u00faltimo d\u00edgito por un 3 se transforma en 23 que es primo. 25 no es un compuesto persistente porque cambiando su&#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":[4],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5980"}],"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=5980"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5980\/revisions"}],"predecessor-version":[{"id":6016,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5980\/revisions\/6016"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5980"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5980"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5980"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}