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 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
|
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 |
import Data.Numbers.Primes (primes) import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 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) -- 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) |
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.
El código se encuentra en GitHub.