{"id":7144,"date":"2022-07-20T06:00:28","date_gmt":"2022-07-20T04:00:28","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7144"},"modified":"2022-07-13T13:41:35","modified_gmt":"2022-07-13T11:41:35","slug":"potencias-perfectas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/potencias-perfectas\/","title":{"rendered":"Potencias perfectas"},"content":{"rendered":"

Un n\u00famero natural n es una potencia perfecta<\/strong> si existen dos n\u00fameros naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son<\/p>\n

\n   4 = 2\u00b2, 8 = 2\u00b3, 9 = 3\u00b2, 16 = 2\u2074, 25 = 5\u00b2, 27 = 3\u00b3, 32 = 2\u2075, \n   36 = 6\u00b2, 49 = 7\u00b2, 64 = 2\u2076, ...\n<\/pre>\n
Definir la sucesi\u00f3n<\/p>\n
\n   potenciasPerfectas :: [Integer]\n<\/pre>\n
cuyos t\u00e9rminos son las potencias perfectas. Por ejemplo,<\/p>\n
\n   take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]\n   potenciasPerfectas !! 3000  ==  7778521\n<\/pre>\n
Definir el procedimiento<\/p>\n
\n   grafica :: Int -> IO ()\n<\/pre>\n
tal que (grafica n) es la representaci\u00f3n gr\u00e1fica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja
\n\"\"<\/a><\/p>\n
Soluciones<\/h4>\n
\nimport Data.List (group)\nimport Data.Numbers.Primes (primeFactors)\nimport Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\npotenciasPerfectas1 :: [Integer]\npotenciasPerfectas1 = filter esPotenciaPerfecta [4..]\n\n-- (esPotenciaPerfecta x) se verifica si x es una potencia perfecta. Por\n-- ejemplo, \n--    esPotenciaPerfecta 36  ==  True\n--    esPotenciaPerfecta 72  ==  False\nesPotenciaPerfecta :: Integer -> Bool\nesPotenciaPerfecta = not . null. potenciasPerfectasDe \n\n-- (potenciasPerfectasDe x) es la lista de pares (a,b) tales que \n-- x = a^b. Por ejemplo,\n--    potenciasPerfectasDe 64  ==  [(2,6),(4,3),(8,2)]\n--    potenciasPerfectasDe 72  ==  []\npotenciasPerfectasDe :: Integer -> [(Integer,Integer)]\npotenciasPerfectasDe n = \n  [(m,k) | m <- takeWhile (\\x -> x*x <= n) [2..]\n         , k <- takeWhile (\\x -> m^x <= n) [2..]\n         , m^k == n]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\npotenciasPerfectas2 :: [Integer]\npotenciasPerfectas2 = [x | x <- [4..], esPotenciaPerfecta2 x]\n\n-- (esPotenciaPerfecta2 x) se verifica si x es una potencia perfecta. Por\n-- ejemplo, \n--    esPotenciaPerfecta2 36  ==  True\n--    esPotenciaPerfecta2 72  ==  False\nesPotenciaPerfecta2 :: Integer -> Bool\nesPotenciaPerfecta2 x = mcd (exponentes x) > 1\n\n-- (exponentes x) es la lista de los exponentes de l factorizaci\u00f3n prima\n-- de x. Por ejemplos,\n--    exponentes 36  ==  [2,2]\n--    exponentes 72  ==  [3,2]\nexponentes :: Integer -> [Int]\nexponentes x = [length ys | ys <- group (primeFactors x)] \n\n-- (mcd xs) es el m\u00e1ximo com\u00fan divisor de la lista xs. Por ejemplo,\n--    mcd [4,6,10]  ==  2\n--    mcd [4,5,10]  ==  1\nmcd :: [Int] -> Int\nmcd = foldl1 gcd\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\npotenciasPerfectas3 :: [Integer]\npotenciasPerfectas3 = mezclaTodas potencias\n\n-- potencias es la lista las listas de potencias de todos los n\u00fameros\n-- mayores que 1 con exponentes mayores que 1. Por ejemplo,\n--    \u03bb> map (take 3) (take 4 potencias)\n--    [[4,8,16],[9,27,81],[16,64,256],[25,125,625]]\npotencias:: [[Integer]]\npotencias = [[n^k | k <- [2..]] | n <- [2..]]\n\n-- (mezclaTodas xss) es la mezcla ordenada sin repeticiones de las\n-- listas ordenadas xss. Por ejemplo,\n--    take 7 (mezclaTodas potencias)  ==  [4,8,9,16,25,27,32]\nmezclaTodas :: Ord a => [[a]] -> [a]\nmezclaTodas = foldr1 xmezcla\n  where xmezcla (x:xs) ys = x : mezcla xs ys\n\n-- (mezcla xs ys) es la mezcla ordenada sin repeticiones de las\n-- listas ordenadas xs e ys. Por ejemplo,\n--    take 7 (mezcla [2,5..] [4,6..])  ==  [2,4,5,6,8,10,11]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)\n                     | x == y = x : mezcla xs ys\n                     | x > y  = y : mezcla (x:xs) ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_potenciasPerfectas :: NonNegative Int -> Bool\nprop_potenciasPerfectas (NonNegative n) =\n  all (== potenciasPerfectas1 !! n)\n      [potenciasPerfectas2 !! n,\n       potenciasPerfectas3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_potenciasPerfectas\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> potenciasPerfectas1 !! 200\n--    28224\n--    (10.56 secs, 8,434,647,368 bytes)\n--    \u03bb> potenciasPerfectas2 !! 200\n--    28224\n--    (0.36 secs, 825,040,416 bytes)\n--    \u03bb> potenciasPerfectas3 !! 200\n--    28224\n--    (0.05 secs, 7,474,280 bytes)\n--    \n--    \u03bb> potenciasPerfectas2 !! 500\n--    191844\n--    (4.16 secs, 9,899,367,112 bytes)\n--    \u03bb> potenciasPerfectas3 !! 500\n--    191844\n--    (0.09 secs, 51,275,464 bytes)\n\n-- En lo que sigue se usa la 3\u00aa soluci\u00f3n\npotenciasPerfectas :: [Integer]\npotenciasPerfectas = potenciasPerfectas3\n\n-- Representaci\u00f3n gr\u00e1fica\n-- ======================\n\ngrafica :: Int -> IO ()\ngrafica n = \n  plotList [ Key Nothing\n           , PNG \"Potencias_perfectas.png\"\n           ]\n           (take n potenciasPerfectas)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Un n\u00famero natural n es una potencia perfecta si existen dos n\u00fameros naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son 4 = 2\u00b2, 8 = 2\u00b3, 9 = 3\u00b2, 16 = 2\u2074, 25 = 5\u00b2, 27 = 3\u00b3, 32 = 2\u2075, 36 = 6\u00b2, 49…<\/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":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7144"}],"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=7144"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7144\/revisions"}],"predecessor-version":[{"id":7145,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7144\/revisions\/7145"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7144"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7144"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}