{"id":4940,"date":"2015-07-09T13:58:59","date_gmt":"2015-07-09T11:58:59","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4940"},"modified":"2015-07-09T13:58:59","modified_gmt":"2015-07-09T11:58:59","slug":"otra-conjetura-de-goldbach-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/otra-conjetura-de-goldbach-en-haskell\/","title":{"rendered":"Otra conjetura de Goldbach en Haskell"},"content":{"rendered":"

En 1752 Goldbach le escribi\u00f3 un carta a Euler en la que conjeturaba que todo n\u00famero impar compuesto se puede escribir como la suma de un primo y el doble de un cuadrado. Por ejemplo,<\/p>\n

\n   9 =  7 + 2\u00d71^2\n   15 =  7 + 2\u00d72^2\n   21 =  3 + 2\u00d73^2\n   25 =  7 + 2\u00d73^2\n   27 = 19 + 2\u00d72^2\n   33 = 31 + 2\u00d71^2\n<\/pre>\n
En la siguiente relaci\u00f3n de ejercicios (elaborada para la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se comprueba con Haskell que la conjetura es falsa.<\/p>\n
\n-- ---------------------------------------------------------------------\n-- Librer\u00edas auxiliares\n-- ---------------------------------------------------------------------\n\nimport Graphics.Gnuplot.Simple\nimport Data.Numbers.Primes (isPrime, primes)\nimport qualified Data.Map as M\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    descomposiciones :: Integer -> [(Integer,Integer)]\n-- tal que (descomposiciones x) es la lista de los pares (p,y) tales que \n-- x = p+2*y^2 con p primo e y entero. Por ejemplo,\n--    descomposiciones 15  ==  [(13,1),(7,2)]\n-- ---------------------------------------------------------------------\n\ndescomposiciones :: Integer -> [(Integer,Integer)]\ndescomposiciones x =\n    [(p,y) | y <- [0..n]\n           , let p = x-2*y^2\n           , isPrime p]\n    where n = ceiling (sqrt ((fromIntegral x)\/2))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir, usando descomposiciones, la lista\n--    contraejemplos1 :: [Integer]\n-- cuyos elementos sean los contraejemplos de la anterior conjetura de\n-- Goldbach. Por ejemplo, \n--    take 2 contraejemplos1  ==  [5777,5993]\n-- ---------------------------------------------------------------------\n\ncontraejemplos1 :: [Integer]\ncontraejemplos1 = \n    [x | x <- [3,5..]\n       , not (isPrime x)\n       , null (descomposiciones x)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    imparesCompuestos :: [Integer]\n-- tal que imparesCompuestos es la lista de los n\u00fameros impares que son\n-- compuestos. Por ejemplo,\n--    take 10 imparesCompuestos  ==  [9,15,21,25,27,33,35,39,45,49]\n-- ---------------------------------------------------------------------\n\nimparesCompuestos :: [Integer]\nimparesCompuestos = aux [3,5..] (tail primes)\n    where aux (x:xs) (y:ys) | x == y    = aux xs ys\n                            | otherwise = x : aux xs (y:ys)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir, usando descomposiciones e imparesCompuestos, la\n-- lista \n--    contraejemplos2 :: [Integer]\n-- cuyos elementos sean los contraejemplos de la anterior conjetura de\n-- Goldbach. Por ejemplo, \n--    take 2 contraejemplos2  ==  [5777,5993]\n-- ---------------------------------------------------------------------\n\ncontraejemplos2 :: [Integer]\ncontraejemplos2 = \n    [x | x <- imparesCompuestos\n       , null (descomposiciones x)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    conjetura :: Integer -> Bool\n-- tal que (conjetura n) se verifica si n es cumple la conjetura. Por\n-- ejemplo, \n--    conjetura 2015  ==  True\n--    conjetura 5777  ==  False\n-- ---------------------------------------------------------------------\n\nconjetura :: Integer -> Bool\nconjetura n = \n    any isPrime (takeWhile (>0) (map (\\i -> n - 2*i*i) [1..]))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir, usando conjetura, la lista \n--    contraejemplos3 :: [Integer]\n-- cuyos elementos sean los contraejemplos de la anterior conjetura de\n-- Goldbach. Por ejemplo, \n--    take 2 contraejemplos3  ==  [5777,5993]\n-- ---------------------------------------------------------------------\n\ncontraejemplos3 :: [Integer]\ncontraejemplos3 = \n    filter (not . conjetura) (filter (not . isPrime) [3,5..])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Comparar la eficiencia de las 3 definiciones de\n-- contraejemplos para calcular el primer contraejemplo.\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    ghci> head contraejemplos1\n--    5777\n--    (0.31 secs, 184659216 bytes)\n--    ghci> head contraejemplos2\n--    5777\n--    (0.27 secs, 146877536 bytes)\n--    ghci> head contraejemplos3\n--    5777\n--    (0.23 secs, 159419472 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    distribucion :: [Integer] -> [(Int,[Integer])]\n-- tal que (distribucion xs) es la lista de pares (n,ys) tales que ys es\n-- la lista de elementos de xs con n descomposiciones como suma de un\n-- primo y es doble del cuadrado de un entero. Por ejemplo,\n--    ghci> distribucion [3,5..100]\n--    [(1,[3,9,17,27,33,57,65,95]),\n--     (2,[5,7,11,15,23,29,35,41,47,51,53,59,71,77,83,87,93,99]),\n--     (3,[13,19,21,25,39,43,45,63,67,81,89]),\n--     (4,[31,37,49,69,73,75,85,97]),\n--     (5,[55]),\n--     (6,[61,79,91])]\n--     ghci> distribucion [2,4..100]\n--     [(0,[6,8,12,14,16,18,22,24,26,28,30,32,36,38,40,42,44,46,48,50,54,\n--          56,58,60,62,64,66,68,70,72,76,78,80,82,84,86,88,90,92,94,96,98]),\n--      (1,[2,4,10,20,34,52,74,100])]\n------------------------------------------------------------------------\n\ndistribucion :: [Integer] -> [(Int,[Integer])]\ndistribucion xs = M.toList (M.map reverse (aux xs M.empty))\n    where aux [] d = d\n          aux (y:ys) d = aux ys (M.insertWith (++) k [y] d)\n                         where k = length (descomposiciones y)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    frecuencias :: [Integer] -> [(Int,Int)]\n-- tal que (frecuencias xs) es la lista de pares (n,y) tales que y es\n-- el n\u00famero de elementos de xs con n descomposiciones como suma de un\n-- primo y es doble del cuadrado de un entero. Por ejemplo,\n--    frecuencias [3,5..100]  ==  [(1,8),(2,18),(3,11),(4,8),(5,1),(6,3)]\n--    frecuencias [2,4..100]  ==  [(0,42),(1,8)]\n-- ---------------------------------------------------------------------\n\nfrecuencias :: [Integer] -> [(Int,Int)]\nfrecuencias xs =\n    [(n,length ys) | (n,ys) <- distribucion xs] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir el procedimiento\n--    dibujoFrecuencias :: Integer -> IO ()\n-- tal que (dibujoFrecuencias n) dibuja las frecuencias de [3,5..n] para\n-- n igual a 1000, 3000 y 6000.\n-- ---------------------------------------------------------------------\n\ndibujoFrecuencias :: Integer -> IO ()\ndibujoFrecuencias n = \n    plotLists []\n              [frecuencias' [3,5..k] | k <- [n,3*n,6*n]]\n    where frecuencias' :: [Integer] -> [(Double,Double)]\n          frecuencias' xs = [(fromIntegral x, fromIntegral y)\n                             | (x,y) <- frecuencias xs]\n<\/pre>\n
El dibujo es \"Goldbach\"<\/a><\/p>\n
Referencias<\/h3>\n