{"id":5320,"date":"2020-01-03T05:30:30","date_gmt":"2020-01-03T03:30:30","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5320"},"modified":"2020-01-10T08:36:47","modified_gmt":"2020-01-10T06:36:47","slug":"teorema-de-liouville-sobre-listas-cucu","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/teorema-de-liouville-sobre-listas-cucu\/","title":{"rendered":"Teorema de Liouville sobre listas CuCu"},"content":{"rendered":"<p>Una <a href=\"http:\/\/bit.ly\/2MxFQfJ\">lista CuCu<\/a> es una lista de n\u00fameros enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que<\/p>\n<pre lang=\"text\">\n   1\u00b3 + 2\u00b3 + 3\u00b3 + 2\u00b3 + 4\u00b3 + 6\u00b3 = (1 + 2 + 3 + 2 + 4 + 6)\u00b2\n<\/pre>\n<p>La <strong>lista de Liouville<\/strong> correspondiente al n\u00famero entero positivo n es la lista formada por el n\u00famero de divisores de cada divisor de n. Por ejemplo, para el n\u00famero 20 se tiene que sus divisores son<\/p>\n<pre lang=\"text\">\n   1, 2, 4, 5, 10, 20\n<\/pre>\n<p>puesto que el n\u00famero de sus divisores es<\/p>\n<ul>\n<li>El  1 tiene 1 divisor (el 1 solamente).<\/li>\n<li>El  2 tiene 2 divisores (el 1 y el 2).<\/li>\n<li>El  4 tiene 3 divisores (el 1, el 2 y el 4).<\/li>\n<li>El  5 tiene 2 divisores (el 1 y el 5).<\/li>\n<li>El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).<\/li>\n<li>El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).<\/li>\n<\/ul>\n<p>la lista de Liouville de 20 es [1, 2, 3, 2, 4, 6] que, como se coment\u00f3 anteriormente, es una lista CuCu.<\/p>\n<p>El <strong>teorema de Lioville<\/strong> afirma que todas las lista de Lioville son CuCu.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   esCuCu :: [Integer] -> Bool\n   liouville :: Integer -> [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(esCuCu xs) se verifica si la lista xs es CuCu; es decir, la suma de los cubos de sus elementos es igual al cuadrado de su suma. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     esCuCu [1,2,3]        ==  True\n     esCuCu [1,2,3,2]      ==  False\n     esCuCu [1,2,3,2,4,6]  ==  True\n<\/pre>\n<ul>\n<li>(liouville n) es la lista de Lioville correspondiente al n\u00famero n. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">  \n     liouville 20  ==  [1,2,3,2,4,6]\n     liouville 60  ==  [1,2,2,3,2,4,4,6,4,6,8,12]\n     length (liouville (product [1..25]))  ==  340032\n<\/pre>\n<p>Comprobar con QuickCheck<\/p>\n<ul>\n<li>que para todo entero positivo n, (liouville (2^n)) es la lista [1,2,3,&#8230;,n+1] y<\/li>\n<li>el teorema de Lioville; es decir, para todo entero positivo n, (liouville n) es una lista CuCu. <\/li>\n<\/ul>\n<p><strong>Nota<\/strong>: Este ejercicio est\u00e1 basado en <a href=\"http:\/\/bit.ly\/2MxFQf\">C\u00f3mo generar conjuntos CuCu<\/a> de Gaussianos.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group, inits, sort)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck\n\nesCuCu :: [Integer] -> Bool\nesCuCu xs = sum (map (^3) xs) == (sum xs)^2\n\n-- 1\u00aa definici\u00f3n de liouville\n-- ==========================\n\nliouville :: Integer -> [Integer]\nliouville n = map numeroDivisores (divisores n)\n\n-- (divisores x) es el conjunto de divisores de los x. Por ejemplo, \n--   divisores 30  ==  [1,2,3,5,6,10,15,30]\ndivisores :: Integer -> [Integer]\ndivisores n = [x | x <- [1..n], n `mod` x == 0]\n\n-- (numeroDivisores x) es el n\u00famero de divisores de x. Por ejemplo, \n--    numeroDivisores 12  ==  6\n--    numeroDivisores 25  ==  3\nnumeroDivisores :: Integer -> Integer\nnumeroDivisores n = genericLength (divisores n) \n\n  -- 2\u00aa definici\u00f3n de liouville\n-- ============================\n\nliouville2 :: Integer -> [Integer]\nliouville2 n = map numeroDivisores2 (divisores2 n)\n\n-- Se usan las funciones\n-- + divisores de \"Conjunto de divisores\" http:\/\/bit.ly\/2OtbFIj\n-- + numeroDivisores de \"N\u00famero de divisores\" http:\/\/bit.ly\/2DgVh74\n\n-- (divisores2 x) es el conjunto de divisores de los x. Por ejemplo, \n--   divisores2 30  ==  [1,2,3,5,6,10,15,30]\ndivisores2 :: Integer -> [Integer]\ndivisores2 = sort\n           . map (product . concat)\n           . sequence\n           . map inits\n           . group\n           . primeFactors\n\n-- (numeroDivisores2 x) es el n\u00famero de divisores de x. Por ejemplo, \n--    numeroDivisores2 12  ==  6\n--    numeroDivisores2 25  ==  3\nnumeroDivisores2 :: Integer -> Integer\nnumeroDivisores2 =\n  product . map ((+1) . genericLength) . group . primeFactors\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (liouville (product [1..11]))\n--    540\n--    (13.66 secs, 7,983,550,640 bytes)\n--    \u03bb> length (liouville2 (product [1..11]))\n--    540\n--    (0.01 secs, 1,255,328 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_Liouville :: Integer -> Property\nprop_Liouville n =\n  n > 0 ==> liouville2 (2^n) == [1..n+1]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_Liouville\n--    +++ OK, passed 100 tests.\n\n-- Teorema de Liouville\n-- ====================\n\n-- La propiedad es\nteorema_Liouville :: Integer -> Property\nteorema_Liouville n =\n  n > 0 ==> esCuCu (liouville n)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck teorema_Liouville\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00a1Oh, tarde viva y quieta<br \/>\nque opuso al panta rhei su nada corre.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Una lista CuCu es una lista de n\u00fameros enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que 1\u00b3 + 2\u00b3 + 3\u00b3 + 2\u00b3 + 4\u00b3 + 6\u00b3 = (1 + 2 + 3&#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":[8,12,258,13,74,10,89,11,247,157,482,14,40,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5320"}],"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=5320"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5320\/revisions"}],"predecessor-version":[{"id":5358,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5320\/revisions\/5358"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5320"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}