Huecos maximales entre primos
Publicado el 19 de enero de 2024 por José A. Alonso

primosYhuecosMaximales :: [(Integer,Integer)]

λ> take 8 primosYhuecosMaximales
[(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]
λ> primosYhuecosMaximales !! 20
(2010733,148)

module Huecos_maximales_entre_primos where

import Data.Numbers.Primes (primes)
import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución
-- ===========

primosYhuecosMaximales1 :: [(Integer,Integer)]
primosYhuecosMaximales1 =
  [(p,huecoPrimo p) | p <- primes, esMaximalHuecoPrimo p]

-- (siguientePrimo x) es el menor primo mayor que x. Por ejemplo,
--    siguientePrimo 7  ==  11
--    siguientePrimo 8  ==  11
siguientePrimo :: Integer -> Integer
siguientePrimo p =
  head (dropWhile (<= p) primes)

-- (huecoPrimo p) es la distancia del primo p hasta el siguiente
-- primo. Por ejemplo,
--    huecoPrimo 7  ==  4
huecoPrimo :: Integer -> Integer
huecoPrimo p = siguientePrimo p - p

-- (esMaximalHuecoPrimo p) se verifica si el hueco primo de p es
-- maximal. Por ejemplo,
--    esMaximalHuecoPrimo  7  ==  True
--    esMaximalHuecoPrimo 11  ==  False
esMaximalHuecoPrimo :: Integer -> Bool
esMaximalHuecoPrimo p =
  and [huecoPrimo n < h | n <- takeWhile (< p) primes]
  where h = huecoPrimo p

-- 2ª solución
-- ===========

primosYhuecosMaximales2 :: [(Integer,Integer)]
primosYhuecosMaximales2 = aux primosYhuecos
  where aux ((x,y):ps) = (x,y) : aux (dropWhile (\(_,b) -> b <= y) ps)

-- primosYhuecos es la lista de los números primos junto son sus
-- huecos. Por ejemplo,
--    λ> take 10 primosYhuecos
--    [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)]
primosYhuecos :: [(Integer,Integer)]
primosYhuecos =
  [(x,y-x) | (x,y) <- zip primes (tail primes)]

-- 3ª solución
-- ===========

primosYhuecosMaximales3 :: [(Integer,Integer)]
primosYhuecosMaximales3 = aux 0 primes
  where aux n (x:y:zs) | y-x > n   = (x,y-x) : aux (y-x) (y:zs)
                       | otherwise = aux n (y:zs)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: [(Integer,Integer)] -> Spec
specG primosYhuecosMaximales = do
  it "e1" $
    take 8 primosYhuecosMaximales `shouldBe`
    [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]

spec :: Spec
spec = do
  describe "def. 1" $ specG primosYhuecosMaximales1
  describe "def. 2" $ specG primosYhuecosMaximales2
  describe "def. 3" $ specG primosYhuecosMaximales3


-- La verificación es
--    λ> verifica
--
--    3 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_primosYhuecosMaximales :: NonNegative Int -> Bool
prop_primosYhuecosMaximales (NonNegative n) =
  all (== primosYhuecosMaximales1 !! n)
      [primosYhuecosMaximales2 !! n,
       primosYhuecosMaximales3 !! n]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=12}) prop_primosYhuecosMaximales
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> primosYhuecosMaximales1 !! 10
--    (9551,36)
--    (2.63 secs, 7,400,316,112 bytes)
--    λ> primosYhuecosMaximales2 !! 10
--    (9551,36)
--    (0.01 secs, 7,060,744 bytes)
--    λ> primosYhuecosMaximales3 !! 10
--    (9551,36)
--    (0.01 secs, 4,000,368 bytes)
--
--    λ> primosYhuecosMaximales2 !! 22
--    (17051707,180)
--    (7.90 secs, 17,275,407,712 bytes)
--    λ> primosYhuecosMaximales3 !! 22
--    (17051707,180)
--    (3.78 secs, 8,808,779,096 bytes)

from itertools import count, islice, pairwise, takewhile
from timeit import Timer, default_timer
from typing import Iterator

from sympy import isprime, nextprime

# 1ª solución
# ===========

# primos() genera la lista de los primos. Por ejemplo,
#    >>> list(islice(primos(), 10))
#    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def primos() -> Iterator[int]:
    return (n for n in count() if isprime(n))

# huecoPrimo(p) es la distancia del primo p hasta el siguiente
# primo. Por ejemplo,
#    huecoPrimo(7)  ==  4
def huecoPrimo(p: int) -> int:
    return nextprime(p) - p

# esMaximalHuecoPrimo(p) se verifica si el hueco primo de p es
# maximal. Por ejemplo,
#    esMaximalHuecoPrimo(7)   ==  True
#    esMaximalHuecoPrimo(11)  ==  False
def esMaximalHuecoPrimo(p: int) -> bool:
    h = huecoPrimo(p)
    return all(huecoPrimo(n) < h for n in takewhile(lambda x: x < p, primos()))

def primosYhuecosMaximales1() -> Iterator[tuple[int, int]] :
    return ((p,huecoPrimo(p)) for p in primos() if esMaximalHuecoPrimo(p))

# 2ª solución
# ===========

# primosYhuecos es la lista de los números primos junto son sus
# huecos. Por ejemplo,
#    >>> list(islice(primosYhuecos(), 10))
#    [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)]
def primosYhuecos() -> Iterator[tuple[int, int]]:
    return ((x,y-x) for (x,y) in pairwise(primos()))

def primosYhuecosMaximales2() -> Iterator[tuple[int, int]]:
    n = 0
    for (x,y) in primosYhuecos():
        if y > n:
            yield (x,y)
            n = y

# Verificación
# ============

def test_primosYhuecosMaximales() -> None:
    r = [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]
    assert list(islice(primosYhuecosMaximales1(), 8)) == r
    assert list(islice(primosYhuecosMaximales2(), 8)) == r
    print("Verificado")

# La verificación es
#    >>> test_primosYhuecosMaximales()
#    Verificado


# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('list(islice(primosYhuecosMaximales1(), 15))')
#    8.08 segundos
#    >>> tiempo('list(islice(primosYhuecosMaximales2(), 15))')
#    0.17 segundos