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
1 2 3 4 5 |
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
1 2 3 4 5 6 7 8 9 |
Primo Hueco 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20 |
Definir la sucesión
1 |
primosYhuecosMaximales :: [(Integer,Integer)] |
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
1 2 3 4 |
λ> 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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.