Ir al contenido principal

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

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

Definir la sucesión

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)

Soluciones

import Data.Numbers.Primes (primes)

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

-- (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

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

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

-- 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)]

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

-- 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)


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

--    λ> primosYhuecosMaximales1 !! 10
--    (9551,36)
--    (6.92 secs, 3392307944 bytes)
--    λ> primosYhuecosMaximales2 !! 10
--    (9551,36)
--    (0.01 secs, 3619140 bytes)
--
--    λ> primosYhuecosMaximales2 !! 20
--    (2010733,148)
--    (3.91 secs, 1,502,737,472 bytes)
--    λ> primosYhuecosMaximales3 !! 20
--    (2010733,148)
--    (2.20 secs, 791,995,512 bytes)

Referencias

Basado en el ejercicio Maximal prime gaps de Programming Praxis.

Otras referencias: