{"id":8375,"date":"2024-01-19T06:00:39","date_gmt":"2024-01-19T04:00:39","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8375"},"modified":"2024-02-02T17:04:17","modified_gmt":"2024-02-02T15:04:17","slug":"19-ene-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-ene-24\/","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 los 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
<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Huecos_maximales_entre_primos where\n\nimport Data.Numbers.Primes (primes)\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\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-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: [(Integer,Integer)] -> Spec\nspecG primosYhuecosMaximales = do\n  it \"e1\" $\n    take 8 primosYhuecosMaximales `shouldBe`\n    [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG primosYhuecosMaximales1\n  describe \"def. 2\" $ specG primosYhuecosMaximales2\n  describe \"def. 3\" $ specG primosYhuecosMaximales3\n\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    3 examples, 0 failures\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
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import count, islice, pairwise, takewhile\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom sympy import isprime, nextprime\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# primos() genera la lista de los primos. Por ejemplo,\n#    >>> list(islice(primos(), 10))\n#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\ndef primos() -> Iterator[int]:\n    return (n for n in count() if isprime(n))\n\n# huecoPrimo(p) es la distancia del primo p hasta el siguiente\n# primo. Por ejemplo,\n#    huecoPrimo(7)  ==  4\ndef huecoPrimo(p: int) -> int:\n    return nextprime(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\ndef esMaximalHuecoPrimo(p: int) -> bool:\n    h = huecoPrimo(p)\n    return all(huecoPrimo(n) < h for n in takewhile(lambda x: x < p, primos()))\n\ndef primosYhuecosMaximales1() -> Iterator[tuple[int, int]] :\n    return ((p,huecoPrimo(p)) for p in primos() if esMaximalHuecoPrimo(p))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# primosYhuecos es la lista de los n\u00fameros primos junto son sus\n# huecos. Por ejemplo,\n#    >>> list(islice(primosYhuecos(), 10))\n#    [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)]\ndef primosYhuecos() -> Iterator[tuple[int, int]]:\n    return ((x,y-x) for (x,y) in pairwise(primos()))\n\ndef primosYhuecosMaximales2() -> Iterator[tuple[int, int]]:\n    n = 0\n    for (x,y) in primosYhuecos():\n        if y > n:\n            yield (x,y)\n            n = y\n\n# Verificaci\u00f3n\n# ============\n\ndef test_primosYhuecosMaximales() -> None:\n    r = [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]\n    assert list(islice(primosYhuecosMaximales1(), 8)) == r\n    assert list(islice(primosYhuecosMaximales2(), 8)) == r\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_primosYhuecosMaximales()\n#    Verificado\n\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('list(islice(primosYhuecosMaximales1(), 15))')\n#    8.08 segundos\n#    >>> tiempo('list(islice(primosYhuecosMaximales2(), 15))')\n#    0.17 segundos\n<\/pre>\n
Referencias<\/b><\/p>\n
Basado en el ejercicio Maximal prime gaps<\/a> de Programming Praxis<\/a>.<\/p>\n
Otras referencias:<\/p>\n