{"id":5437,"date":"2020-01-27T09:23:15","date_gmt":"2020-01-27T07:23:15","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5437"},"modified":"2020-02-03T09:39:13","modified_gmt":"2020-02-03T07:39:13","slug":"la-conjetura-de-mertens","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/la-conjetura-de-mertens\/","title":{"rendered":"La conjetura de Mertens"},"content":{"rendered":"<p>Un n\u00famero entero n es <a href=\"http:\/\/bit.ly\/2RrYxnZ\">libre de cuadrados<\/a> si no existe un n\u00famero primo p tal que p\u00b2 divide a n; es decir, los factores primos de n son todos distintos.<\/p>\n<p>La <a href=\"http:\/\/bit.ly\/37u64bG\">funci\u00f3n de M\u00f6bius<\/a> \u03bc(n) est\u00e1 definida para todos los enteros positivos como sigue:<\/p>\n<ul>\n<li>\u03bc(n) = 1 si n es libre de cuadrados y tiene un n\u00famero par de factores primos. <\/li>\n<li>\u03bc(n) = -1 si n es libre de cuadrados y tiene un n\u00famero impar de factores primos. <\/li>\n<li>\u03bc(n) = 0 si n no es libre de cuadrados.<\/li>\n<\/ul>\n<p>Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, &#8230;<\/p>\n<p>La <a href=\"http:\/\/bit.ly\/2GmD5uf\">funci\u00f3n de Mertens<\/a> M(n) est\u00e1 definida para todos los enteros positivos como la suma de \u03bc(k) para 1 \u2264 k \u2264 n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, &#8230;<\/p>\n<p>La <a href=\"http:\/\/bit.ly\/2RqJk6Q\">conjetura de Mertens<\/a> afirma que<\/p>\n<blockquote><p>\nPara todo entero x mayor que 1, el valor absoluto de la funci\u00f3n de Mertens en x es menor que la ra\u00edz cuadrada de x.\n<\/p><\/blockquote>\n<p>La conjetura fue planteada por Franz Mertens en 1897. Riele  Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta m\u00e1s o menos a partir de <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=10%5E%7B10%5E%7B64%7D%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"10^{10^{64}}\" class=\"latex\" \/>, cifra que luego de algunos refinamientos se redujo a <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=10%5E%7B10%5E%7B40%7D%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"10^{10^{40}}\" class=\"latex\" \/>.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   mobius :: Integer -> Integer\n   mertens :: Integer -> Integer\n   graficaMertens :: Integer -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(mobius n) es el valor de la funci\u00f3n de M\u00f6bius en n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     mobius 6   ==  1\n     mobius 30  ==  -1\n     mobius 12  ==  0\n<\/pre>\n<ul>\n<li>(mertens n) es el valor de la funci\u00f3n de Mertens en n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     mertens 1     ==  1\n     mertens 2     ==  0\n     mertens 3     ==  -1\n     mertens 5     ==  -2\n     mertens 661   ==  -11\n     mertens 1403  ==  11\n<\/pre>\n<ul>\n<li>(graficaMertens n) dibuja la gr\u00e1fica de la funci\u00f3n de Mertens, la ra\u00edz cuadrada y el opuestos de la ra\u00edz cuadrada para los n primeros n enteros positivos. Por ejemplo, (graficaMertens 1000) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/01\/La_conjetura_de_Mertens.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/01\/La_conjetura_de_Mertens.png?resize=640%2C480\" alt=\"\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-5438\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/01\/La_conjetura_de_Mertens.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/01\/La_conjetura_de_Mertens.png?resize=300%2C225&amp;ssl=1 300w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a> <\/li>\n<\/ul>\n<p>Comprobar con QuickCheck la conjetura de Mertens.<\/p>\n<p><strong>Nota:<\/strong> El ejercicio est\u00e1 basado en <a href=\"http:\/\/bit.ly\/36vP2si\">La conjetura de Merterns y su relaci\u00f3n con un n\u00famero tan raro como extremada y colosalmente grande<\/a> publicado por <a href=\"https:\/\/twitter.com\/alvy\">@Alvy<\/a> la semana pasada en <a href=\"https:\/\/www.microsiervos.com\">Microsiervos<\/a>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck\nimport Graphics.Gnuplot.Simple\n\nmobius :: Integer -> Integer\nmobius n | tieneRepetidos xs = 0\n         | otherwise         = (-1)^(length xs)\n  where xs = primeFactors n\n\ntieneRepetidos :: [Integer] -> Bool\ntieneRepetidos xs =\n  or [x == y | (x,y) <- zip xs (tail xs)]\n        \nmertens :: Integer -> Integer\nmertens n = sum (map mobius [1..n])\n\n-- Definici\u00f3n de graficaMertens\n-- ============================\n\ngraficaMertens :: Integer -> IO ()\ngraficaMertens n = do\n  plotLists [ Key Nothing\n            , Title \"Conjetura de Mertens\"\n            , PNG \"La_conjetura_de_Mertens.png\"\n            ]\n            [ [mertens k | k <- [1..n]]\n            , raices\n            , map negate raices\n            ]\n    \n  where\n    raices = [ceiling (sqrt k) | k <- [1..fromIntegral n]]\n\n-- Conjetura de Mertens\n-- ====================\n\n-- La conjetura es\nconjeturaDeMertens :: Integer -> Property\nconjeturaDeMertens n =\n  n > 1\n  ==>\n  abs (mertens n) < ceiling (sqrt n')\n  where n' = fromIntegral n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck conjeturaDeMertens\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00abEl control de la complejidad es la esencia de la programaci\u00f3n inform\u00e1tica.\u00bb <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Brian_Kernighan\">Brian Kernighan<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Un n\u00famero entero n es libre de cuadrados si no existe un n\u00famero primo p tal que p\u00b2 divide a n; es decir, los factores primos de n son todos distintos. La funci\u00f3n de M\u00f6bius \u03bc(n) est\u00e1 definida para todos los enteros positivos como sigue: \u03bc(n) = 1 si n es libre de cuadrados 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":[4],"tags":[130,322,8,183,376,28,10,169,11,375,247,236,40,45,146,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5437"}],"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=5437"}],"version-history":[{"count":10,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5437\/revisions"}],"predecessor-version":[{"id":5527,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5437\/revisions\/5527"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}