{"id":3964,"date":"2018-04-10T06:00:18","date_gmt":"2018-04-10T04:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3964"},"modified":"2022-03-26T11:30:45","modified_gmt":"2022-03-26T09:30:45","slug":"alturas-primas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/alturas-primas\/","title":{"rendered":"Alturas primas"},"content":{"rendered":"<p>Se considera una enumeraci\u00f3n de los n\u00fameros primos:<\/p>\n<pre lang=\"text\">\n    p(1)=2,  p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,...\n<\/pre>\n<p>Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorizaci\u00f3n de x en n\u00fameros primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2&#215;5^3&#215;7^1 y la de 34 tiene es 7, pues 34 = 2&#215;17. Adem\u00e1s, se define la altura prima de 1 como 0.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   alturaPrima        :: Integer -> Integer\n   alturasPrimas      :: Integer -> [Integer]\n   graficaAlturaPrima :: Integer -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(alturaPrima x) es la altura prima de x. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     alturaPrima 3500  ==  4\n     alturaPrima 34    ==  7\n<\/pre>\n<ul>\n<li>(alturasPrimas n) es la lista de las altura prima de los primeros n n\u00fameros enteros positivos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     alturasPrimas 15  ==  [0,1,2,1,3,2,4,1,2,3,5,2,6,4,3]\n     maximum (alturasPrimas 10000)  ==  1229\n     maximum (alturasPrimas 20000)  ==  2262\n     maximum (alturasPrimas 30000)  ==  3245\n     maximum (alturasPrimas 40000)  ==  4203\n<\/pre>\n<ul>\n<li>(graficaAlturaPrima n) dibuja las alturas primas de los n\u00fameros entre 2 y n. Por ejemplo, (graficaAlturaPrima 500) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png?resize=640%2C480\" alt=\"Alturas_primas\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3966\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/04\/Alturas_primas.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Data.Numbers.Primes (isPrime, primes, primeFactors)\nimport Data.Array\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa definicio\u0144 de alturaPrima\n-- ============================\n\nalturaPrima :: Integer -> Integer\nalturaPrima 1 = 0\nalturaPrima n = indice (mayorFactorPrimo n)\n\n-- (mayorFactorPrimo n) es el mayor factor primo de n. Por ejemplo,\n--    mayorFactorPrimo 3500  ==  7\n--    mayorFactorPrimo 34    ==  17\nmayorFactorPrimo :: Integer -> Integer\nmayorFactorPrimo = last . primeFactors\n\n-- (indice p) es el \u00edndice de p en la sucesi\u00f3n de los n\u00fameros\n-- primos. Por ejemplo,\n--    indice 7   ==  4\n--    indice 17  ==  7\nindice :: Integer -> Integer\nindice p = genericLength (takeWhile (<=p) primes)\n\n-- 2\u00aa definicio\u0144 de alturaPrima\n-- ============================\n\nalturaPrima2 :: Integer -> Integer\nalturaPrima2 n = v ! n\n  where v = array (1,n) [(i,f i) | i <- [1..n]]\n        f 1 = 0\n        f k | isPrime k = indice2 k\n            | otherwise = v ! (k `div` (head (primeFactors k)))\n\nindice2 :: Integer -> Integer\nindice2 p = head [n | (x,n) <- indicesPrimos, x == p]\n\n-- indicesPrimos es la suceci\u00f3n formada por los n\u00fameros primos y sus\n-- \u00edndices. Por ejemplo,\n--    \u03bb> take 10 indicesPrimos\n--    [(2,1),(3,2),(5,3),(7,4),(11,5),(13,6),(17,7),(19,8),(23,9),(29,10)]\nindicesPrimos :: [(Integer,Integer)]\nindicesPrimos = zip primes [1..]\n\n-- 1\u00aa definici\u00f3n de alturasPrimas\n-- ==============================\n\nalturasPrimas :: Integer -> [Integer]\nalturasPrimas n = map alturaPrima [1..n]\n\n-- 2\u00aa definici\u00f3n de alturasPrimas\n-- ==============================\n\nalturasPrimas2 :: Integer -> [Integer]\nalturasPrimas2 n = elems v \n  where v = array (1,n) [(i,f i) | i <- [1..n]]\n        f 1 = 0\n        f k | isPrime k = indice2 k\n            | otherwise = v ! (k `div` (head (primeFactors k)))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum (alturasPrimas 20000)\n--    2262\n--    (29.97 secs, 13,179,984,536 bytes)\n--    \u03bb> maximum (alturasPrimas2 20000)\n--    2262\n--    (2.11 secs, 455,259,448 bytes)\n\n-- Definici\u00f3n de graficaAlturaPrima\n-- ================================\n\ngraficaAlturaPrima :: Integer -> IO ()\ngraficaAlturaPrima n =\n  plotList [ Key Nothing\n           , PNG \"Alturas_primas.png\"\n           ]\n           (alturasPrimas2 n)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Se considera una enumeraci\u00f3n de los n\u00fameros primos: p(1)=2, p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,&#8230; Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorizaci\u00f3n de x en n\u00fameros primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2&#215;5^3&#215;7^1 y&#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":[5],"tags":[250,8,286,30,258,376,71,174,134,10,42,11,309,247,173,34,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3964"}],"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=3964"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3964\/revisions"}],"predecessor-version":[{"id":3982,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3964\/revisions\/3982"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3964"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3964"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3964"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}