Huecos maximales entre primos

El hueco de un número primo 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úmeros son

   Primo Hueco
    2    1
    3    2
    7    4
   11    2

Primo Hueco

2 1

3 2

7 4

11 2

El hueco de un número primo p es maximal si es mayor que los huecos de todos los números 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

   Primo Hueco
     2    1
     3    2
     7    4
    23    6
    89    8
   113   14
   523   18
   887   20

Primo Hueco

2 1

3 2

7 4

23 6

89 8

113 14

523 18

887 20

Definir la sucesión

   primosYhuecosMaximales :: [(Integer,Integer)]

1	primosYhuecosMaximales :: [(Integer,Integer)]

cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,

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

λ> take 8 primosYhuecosMaximales

[(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]

λ> primosYhuecosMaximales !! 20

(2010733,148)

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

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)

Soluciones en Python

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

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

Referencias

Basado en el ejercicio Maximal prime gaps de Programming Praxis.

Otras referencias:

C. Caldwell, The gaps between primes.
J.K. Andersen, Maximal prime gaps.
N.J.A. Sloane, Sequence A002386 en OEIS.
N.J.A. Sloane, Sequence A005250 en OEIS.
E.W. Weisstein, Prime gaps en MathWorld.

Huecos maximales entre primos

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico