{"id":3889,"date":"2018-03-21T06:00:07","date_gmt":"2018-03-21T04:00:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3889"},"modified":"2022-03-26T11:31:09","modified_gmt":"2022-03-26T09:31:09","slug":"conjetura-de-goldbach-2018","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjetura-de-goldbach-2018\/","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","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\/3889"}],"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=3889"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3889\/revisions"}],"predecessor-version":[{"id":3918,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3889\/revisions\/3918"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3889"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3889"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3889"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}