{"id":7151,"date":"2022-07-25T06:00:00","date_gmt":"2022-07-25T04:00:00","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7151"},"modified":"2022-07-18T17:50:43","modified_gmt":"2022-07-18T15:50:43","slug":"huecos-maximales-entre-primos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/huecos-maximales-entre-primos\/","title":{"rendered":"Huecos maximales entre primos"},"content":{"rendered":"

El hueco de un n\u00famero primo<\/strong> p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros n\u00fameros son<\/p>\n

\n   Primo Hueco\n    2    1\n    3    2\n    7    4\n   11    2\n<\/pre>\n
El hueco de un n\u00famero primo p es maximal<\/strong> si es mayor que  huecos de todos los n\u00fameros menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es<\/p>\n
\n   Primo Hueco\n     2    1\n     3    2\n     7    4\n    23    6\n    89    8\n   113   14\n   523   18\n   887   20\n<\/pre>\n
Definir la sucesi\u00f3n<\/p>\n
\n   primosYhuecosMaximales :: [(Integer,Integer)]\n<\/pre>\n
cuyos elementos son los n\u00fameros primos con huecos maximales junto son sus huecos. Por ejemplo,<\/p>\n
\n   \u03bb> take 8 primosYhuecosMaximales\n   [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]\n   \u03bb> primosYhuecosMaximales !! 20\n   (2010733,148)\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.Numbers.Primes (primes)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales1 :: [(Integer,Integer)]\nprimosYhuecosMaximales1 = \n  [(p,huecoPrimo p) | p <- primes, esMaximalHuecoPrimo p]\n\n-- (siguientePrimo x) es el menor primo mayor que x. Por ejemplo,\n--    siguientePrimo 7  ==  11\n--    siguientePrimo 8  ==  11\nsiguientePrimo :: Integer -> Integer\nsiguientePrimo p =\n  head (dropWhile (<= p) primes)\n\n-- (huecoPrimo p) es la distancia del primo p hasta el siguiente\n-- primo. Por ejemplo,\n--    huecoPrimo 7  ==  4\nhuecoPrimo :: Integer -> Integer\nhuecoPrimo p = siguientePrimo p - p\n\n-- (esMaximalHuecoPrimo p) se verifica si el hueco primo de p es\n-- maximal. Por ejemplo,\n--    esMaximalHuecoPrimo  7  ==  True\n--    esMaximalHuecoPrimo 11  ==  False\nesMaximalHuecoPrimo :: Integer -> Bool\nesMaximalHuecoPrimo p =\n  and [huecoPrimo n < h | n <- takeWhile (< p) primes]\n  where h = huecoPrimo p\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales2 :: [(Integer,Integer)]\nprimosYhuecosMaximales2 = aux primosYhuecos\n  where aux ((x,y):ps) = (x,y) : aux (dropWhile (\\(_,b) -> b <= y) ps)\n\n-- primosYhuecos es la lista de los n\u00fameros primos junto son sus\n-- huecos. Por ejemplo, \n--    \u03bb> take 10 primosYhuecos\n--    [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)]\nprimosYhuecos :: [(Integer,Integer)]\nprimosYhuecos =\n  [(x,y-x) | (x,y) <- zip primes (tail primes)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nprimosYhuecosMaximales3 :: [(Integer,Integer)]\nprimosYhuecosMaximales3 = aux 0 primes\n  where aux n (x:y:zs) | y-x > n   = (x,y-x) : aux (y-x) (y:zs)\n                       | otherwise = aux n (y:zs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosYhuecosMaximales :: NonNegative Int -> Bool\nprop_primosYhuecosMaximales (NonNegative n) =\n  all (== primosYhuecosMaximales1 !! n)\n      [primosYhuecosMaximales2 !! n,\n       primosYhuecosMaximales3 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=12}) prop_primosYhuecosMaximales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosYhuecosMaximales1 !! 10\n--    (9551,36)\n--    (2.63 secs, 7,400,316,112 bytes)\n--    \u03bb> primosYhuecosMaximales2 !! 10\n--    (9551,36)\n--    (0.01 secs, 7,060,744 bytes)\n--    \u03bb> primosYhuecosMaximales3 !! 10\n--    (9551,36)\n--    (0.01 secs, 4,000,368 bytes)\n--    \n--    \u03bb> primosYhuecosMaximales2 !! 22\n--    (17051707,180)\n--    (7.90 secs, 17,275,407,712 bytes)\n--    \u03bb> primosYhuecosMaximales3 !! 22\n--    (17051707,180)\n--    (3.78 secs, 8,808,779,096 bytes)\n<\/pre>\n
Referencias<\/h4>\n
Basado en el ejercicio Maximal prime gaps<\/a> de
\nProgramming Praxis<\/a>.<\/p>\n
Otras referencias<\/p>\n