{"id":5753,"date":"2020-04-01T08:02:42","date_gmt":"2020-04-01T06:02:42","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5753"},"modified":"2022-03-26T11:28:34","modified_gmt":"2022-03-26T09:28:34","slug":"conjetura-de-goldbach","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjetura-de-goldbach\/","title":{"rendered":"Conjetura de Goldbach"},"content":{"rendered":"<p>Una forma de la <a href=\"http:\/\/bit.ly\/2GJz2Yt\">conjetura de Golbach<\/a> afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres n\u00fameros primos.<\/p>\n<p>Si se define el <strong>\u00edndice de Goldbach<\/strong> de n > 1 como la m\u00ednima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los \u00edndices de Goldbach de los enteros mayores que 1 son menores que 4.<\/p>\n<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   indiceGoldbach  :: Int -> Int\n   graficaGoldbach :: Int -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(indiceGoldbach n) es el \u00edndice de Goldbach de n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     indiceGoldbach 2                        ==  1\n     indiceGoldbach 4                        ==  2\n     indiceGoldbach 27                       ==  3\n     sum (map indiceGoldbach [2..5000])      ==  10619\n     maximum (map indiceGoldbach [2..5000])  ==  3\n<\/pre>\n<ul>\n<li>(graficaGoldbach n) dibuja la gr\u00e1fica de los \u00edndices de Goldbach de los n\u00fameros entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png?resize=640%2C480\" alt=\"Conjetura_de_Goldbach_150\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3892\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/03\/Conjetura_de_Goldbach_150.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<p>Comprobar con QuickCheck la conjetura de Goldbach anterior.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\nimport Data.Numbers.Primes\nimport Graphics.Gnuplot.Simple\nimport Test.QuickCheck\n\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nindiceGoldbach :: Int -> Int\nindiceGoldbach n =\n  minimum (map length (particiones n))\n\nparticiones :: Int -> [[Int]]\nparticiones n = v ! n where\n  v = array (0,n) [(i,f i) | i <- [0..n]]\n    where f 0 = [[]]\n          f m = [x:y | x <- xs, \n                       y <- v ! (m-x), \n                       [x] >= take 1 y]\n            where xs = reverse (takeWhile (<= m) primes)\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nindiceGoldbach2 :: Int -> Int\nindiceGoldbach2 x =\n  head [n | n <- [1..], esSumaDe x n]\n\n-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n\n-- primos. Por ejemplo,\n--    esSumaDe 2  1  ==  True\n--    esSumaDe 4  1  ==  False\n--    esSumaDe 4  2  ==  True\n--    esSumaDe 27 2  ==  False\n--    esSumaDe 27 3  ==  True\nesSumaDe :: Int -> Int -> Bool\nesSumaDe x 1 = isPrime x\nesSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nindiceGoldbach3 :: Int -> Int\nindiceGoldbach3 x =\n  head [n | n <- [1..], esSumaDe3 x n]\n\nesSumaDe3 :: Int -> Int -> Bool\nesSumaDe3 x n = a ! (x,n) where\n  a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]\n  f i 1 = isPrime i\n  f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\nindiceGoldbach4 :: Int -> Int\nindiceGoldbach4 n = v ! n where\n  v = array (2,n) [(i,f i) | i <- [2..n]]\n  f i | isPrime i = 1\n      | otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> sum (map indiceGoldbach [2..80])\n--    142\n--    (2.66 secs, 1,194,330,496 bytes)\n--    \u03bb> sum (map indiceGoldbach2 [2..80])\n--    142\n--    (0.01 secs, 1,689,944 bytes)\n--    \u03bb> sum (map indiceGoldbach3 [2..80])\n--    142\n--    (0.03 secs, 27,319,296 bytes)\n--    \u03bb> sum (map indiceGoldbach4 [2..80])\n--    142\n--    (0.03 secs, 47,823,656 bytes)\n--    \n--    \u03bb> sum (map indiceGoldbach2 [2..1000])\n--    2030\n--    (0.10 secs, 200,140,264 bytes)\n--    \u03bb> sum (map indiceGoldbach3 [2..1000])\n--    2030\n--    (3.10 secs, 4,687,467,664 bytes)\n\n-- Gr\u00e1fica\n-- =======\n\ngraficaGoldbach :: Int -> IO ()\ngraficaGoldbach n =\n  plotList [ Key Nothing\n           , XRange (2,fromIntegral n)\n           , PNG (\"Conjetura_de_Goldbach_\" ++ show n ++ \".png\")\n           ]\n           [indiceGoldbach2 k | k <- [2..n]]\n\n-- Comprobaci\u00f3n de la conjetura de Goldbach\n-- ========================================\n\n-- La propiedad es\nprop_Goldbach :: Int -> Property\nprop_Goldbach x =\n  x >= 2 ==> indiceGoldbach2 x < 4\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_Goldbach\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=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00abLa diferencia entre los matem\u00e1ticos y los f\u00edsicos es que despu\u00e9s de que los f\u00edsicos prueban un gran resultado piensan que es fant\u00e1stico, pero despu\u00e9s de que los matem\u00e1ticos prueban un gran resultado piensan que es trivial.\u00bb <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Lucien_Szpiro\">Lucien Szpiro<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres n\u00fameros primos. Si se define el \u00edndice de Goldbach de n > 1 como la m\u00ednima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de&#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":[250,8,286,376,71,174,28,10,42,340,169,11,309,173,32,47,34,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5753"}],"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=5753"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5753\/revisions"}],"predecessor-version":[{"id":5778,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5753\/revisions\/5778"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5753"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5753"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5753"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}