Menu Close

Buenos primos

La sucesión de los números primos es

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

Las parejas de primos equidistantes de 5 en dicha sucesión son (3, 7) y (2, 11). Se observa que el cuadrado de 5 es mayor que el producto de los elementos de dichas parejas; es decir,

   5^2 = 25 > 21 = 3 x 7
   5^2 = 25 > 22 = 2 x 11

En cambio, el 7 tiene una pareja de primos equidistantes (la (5, 11)) cuyo producto es mayor que el cuadrado de 7.

   7^2 = 49 < 55 = 5 x 11

Un buen primo es un número primo cuyo cuadrado es mayor que el producto de dos primos cualesquiera equidistantes de él en la sucesión de primos. Por ejemplo, 5 es un buen primo pero 7 no lo es.

Definir las funciones

   esBuenPrimo  :: Integer -> Bool
   buenosPrimos :: [Integer]

tales que

  • (esBuenPrimo n) se verifica si n es un buen primo. Por ejemplo,
     esBuenPrimo 5        ==  True
     esBuenPrimo 7        ==  False
     esBuenPrimo 8746811  ==  True
  • buenosPrimos es la lista de los buenos primos. Por ejemplo,
     λ> take 12 buenosPrimos
     [2,5,11,17,29,37,41,53,59,67,71,97]

Comprobar con QuickCheck que la lista de los buenos primos es infinita; es decir, para cualquier entero positivo n existe un número mayor que n que es un buen primo.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck (Property, (==>), quickCheck)
 
esBuenPrimo :: Integer -> Bool
esBuenPrimo n =
  n == y && and [n^2 > x * y | (x, y) <- zip (reverse xs) ys]
  where (xs,y:ys) = span (< n) primes
 
buenosPrimos :: [Integer]
buenosPrimos = filter esBuenPrimo [2..]
 
-- La propiedad es
prop_buenosPrimos :: Integer -> Property
prop_buenosPrimos n =
  n > 0 ==> any esBuenPrimo [n+1..]
 
-- La comprobación es
--    λ> quickCheck prop_buenosPrimos
--    +++ OK, passed 100 tests.
Medio

5 soluciones de “Buenos primos

  1. Rubén Muñoz Mkrtchian
    import Test.QuickCheck
    import Data.Numbers.Primes
     
    esBuenPrimo :: Integer -> Bool
    esBuenPrimo n
      | not (isPrime n) = False
      | otherwise       = not (any (> n^2) (prodPrimosEquidistantes n))
     
    -- prodPrimosEquidistantes es la lista de los valores que se obtienen como
    -- producto de las parejas de primos equidistantes al primo n.
     
    prodPrimosEquidistantes :: Integer -> [Integer]
    prodPrimosEquidistantes n = 
      take posicion [x * y | (x,y) <- zip (nPrimos n) (reverse (nPrimos n))]
      where posicion  = pos n primes
            nPrimos n = take (2 * posicion + 1) primes
     
    -- pos n xs da como valor la posición que ocupa el elemento n en la lista xs.
     
    pos :: Integer -> [Integer] -> Int
    pos n (x:xs)
      | n == x    = 0
      | otherwise = 1 + pos n xs
     
    buenosPrimos :: [Integer]
    buenosPrimos = filter esBuenPrimo primes
     
    propBuenosPrimos :: Integer -> Bool
    propBuenosPrimos n = any esBuenPrimo [n..]
     
    -- La comprobación es:
    -- λ> quickCheck propBuenosPrimos
    -- +++ OK, passed 100 tests.
  2. Ángel Ruiz
    import Data.List           (elemIndex)
    import Data.Array          (listArray,(!))
    import Test.QuickCheck     (quickCheck,Positive(..))
    import Data.Numbers.Primes (isPrime,primes)
     
    -- 1ª definición
    esBuenPrimo1 :: Integer -> Bool
    esBuenPrimo1 n =
      isPrime n && and [n^2 > p!!(m-i) * p!!(m+i) | i <- [1..m]]
      where p      = primes 
            Just m = elemIndex n p
     
    -- 2ª definición
    esBuenPrimo2 :: Integer -> Bool
    esBuenPrimo2 n =
      isPrime n && not (any (n^2 <) (zipWith (*) ps (reverse ps)))
      where p      = primes
            Just m = elemIndex n p
            ps     = take (2*m + 1) p
     
    -- 3ª definición (con array)
    esBuenPrimo3 :: Integer -> Bool
    esBuenPrimo3 n =
      let a = n^2 in isPrime n && and [a > p!(m-i) * p!(m+i) | i <- [1..m]]
      where ps     = primes
            Just m = elemIndex n ps
            p      = listArray (0,2*m) ps
     
    -- Comparación de eficiencia
    -- =========================
     
    -- λ> esBuenPrimo1 25561
    -- True
    -- (2.27 secs, 19,398,616 bytes)
    -- λ> esBuenPrimo2 25561
    -- True
    -- (0.11 secs, 17,714,216 bytes)
    -- λ> esBuenPrimo3 25561
    -- True
    -- (0.13 secs, 18,163,080 bytes)
     
    -- Equivalencia de las soluciones
    -- ==============================
     
    -- La propiedad es
    prop_equiv :: Positive Integer -> Bool
    prop_equiv (Positive n) =
      esBuenPrimo1 n == esBP2 && esBP2 == esBuenPrimo3 n
      where esBP2 = esBuenPrimo2 n
     
    -- La comprobación es
    --    λ> quickCheck prop_equiv
    --    +++ OK, passed 100 tests.
     
    -- Definición
    -- ==========
     
    -- En lo que sigue usaremos la 3ª definición.
    esBuenPrimo :: Integer -> Bool
    esBuenPrimo = esBuenPrimo3
     
    buenosPrimos :: [Integer]
    buenosPrimos = filter esBuenPrimo primes
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_buenosPrimos :: Positive Integer -> Bool
    prop_buenosPrimos (Positive n) = any esBuenPrimo [n+1..]
     
    -- La comprobación es
    --    λ> quickCheck prop_buenosPrimos
    --    +++ OK, passed 100 tests.
  3. Maria Ruiz
    import Data.Numbers.Primes
    import Test.QuickCheck
     
    -- (equidistantes n) es la lista de parejas de primos equidistantes a n,
    -- si n es primo; y [], en caso contrario. Por ejemplo,
    --   equidistantes 5  == [(3,7),(2,11)]
    --   equidistantes 7  == [(5,11),(3,13),(2,17)]
    --   equidistantes 19 == [(17,23),(13,29),(11,31),(7,37),(5,41),(3,43),(2,47)]
     
    equidistantes :: Integer -> [(Integer,Integer)]
    equidistantes n | isPrime n = zip (reverse ps) qs
                    | otherwise = []
      where ps = takeWhile (<n) primes
            m = length ps
            qs = take m (drop (m+1) primes)
     
    esBuenPrimo :: Integer -> Bool
    esBuenPrimo p = all test (equidistantes p)
      where n = p^2
            test (x,y) = x*y < n
     
    buenosPrimos :: [Integer]
    buenosPrimos = filter esBuenPrimo primes
     
    propBuenosPrimos :: Integer -> Bool
    propBuenosPrimos n = any esBuenPrimo [n..]
     
    -- quickCheck propBuenosPrimos
    -- +++ OK, passed 100 tests.
  4. Inés mora Caro
    import Test.QuickCheck
    import Data.List
    import Data.Char
    import Data.Numbers.Primes
     
     
    -- Un buen primo es un número primo cuyo cuadrado es mayor que el producto
    -- de dos primos cualesquiera equidistantes de él en la sucesión de primos.
    -- Por ejemplo, 5 es un buen primo pero 7 no lo es.
     
    esBuenPrimo :: Integer -> Bool
    esBuenPrimo n | isPrime n = all (<(n*n)) (listaPrimosDos n)
                  | otherwise = False
     
    listaPrimosDos :: Integer -> [Integer]
    listaPrimosDos n = zipWith (*) menores mayores
                   where mayores = dropWhile (<=n) primes
                         menores = reverse (takeWhile (<n) primes)
     
     
    buenosPrimos :: [Integer]
    buenosPrimos = filter esBuenPrimo [2..]
     
     
    -- Comprobar con QuickChek que la lista de los buenos primos es infinita;
    -- es decir, para cualquier entero positivo n existe un número mayor que n que
    -- es un buen primo.
     
    prop_buenosPrimos :: Integer -> Property
    prop_buenosPrimos n = n > 1 ==> any esBuenPrimo [n+1..]
     
    -- λ> quickCheck prop_buenosPrimos
    -- +++ OK, passed 100 tests.
  5. Joaquín Infante Rodríguez
    import Data.List
    import Data.Numbers.Primes 
     
     
    equidistantes :: Integer -> (Integer,Integer)
    equidistantes x  = (last (takeWhile (<x) xs), head (dropWhile (<=x) xs))
                         where xs = 1:primes
     
    esBuenPrimo  :: Integer -> Bool
    esBuenPrimo 1 = False
    esBuenPrimo x = elem x  (takeWhile (<=x) primes)
                            && (x^2) > ((fst (equidistantes x)) * (snd (equidistantes x)))
     
    buenosPrimos :: [Integer]
    buenosPrimos = [x | x<-[2..] , esBuenPrimo x]
     
     
    prop_buenosPrimos :: Integer -> Property
    prop_buenosPrimos n =   n > 0 ==> any esBuenPrimo [n+1..]

Leave a Reply to Maria Ruiz Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.