Números consecutivos compuestos

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

   menorSerieCompuesta :: Integer -> (Integer,Integer)

1	menorSerieCompuesta :: Integer -> (Integer,Integer)

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

   menorSerieCompuesta 3    ==  (8,10)
   menorSerieCompuesta 4    ==  (24,27)
   menorSerieCompuesta 5    ==  (24,28)
   menorSerieCompuesta 150  ==  (4652354,4652503)

menorSerieCompuesta 3 == (8,10)

menorSerieCompuesta 4 == (24,27)

menorSerieCompuesta 5 == (24,28)

menorSerieCompuesta 150 == (4652354,4652503)

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

-- 1ª definición
-- =============

menorSerieCompuesta1 :: Integer -> (Integer,Integer)
menorSerieCompuesta1 n = (x,x+n-1)
  where x = head [y | y <- [1..]
                    , esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool
esCompuesta xs =  all (not . isPrime) xs

-- 2ª definición
-- =============

menorSerieCompuesta2 :: Integer -> (Integer,Integer)
menorSerieCompuesta2 n = (x+1,x+n)
  where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)
                            , q - p >= n + 1]

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

--    λ> menorSerieCompuesta1 75
--    (155922,155996)
--    (12.16 secs, 30,378,380,552 bytes)
--    λ> menorSerieCompuesta2 75
--    (155922,155996)
--    (0.07 secs, 89,813,752 bytes)


-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_menorSerieCompuesta :: Integer -> Property
prop_menorSerieCompuesta n =
  n > 1 ==> x == y || y == z
  where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

-- La comprobación es
--    λ> quickCheck prop_menorSerieCompuesta
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª definición

-- =============

menorSerieCompuesta1 :: Integer -> (Integer,Integer)

menorSerieCompuesta1 n = (x,x+n-1)

where x = head [y | y <- [1..]

, esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool

esCompuesta xs = all (not . isPrime) xs

-- 2ª definición

-- =============

menorSerieCompuesta2 :: Integer -> (Integer,Integer)

menorSerieCompuesta2 n = (x+1,x+n)

where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)

, q - p >= n + 1]

-- Comparación de eficiencia

-- =========================

-- λ> menorSerieCompuesta1 75

-- (155922,155996)

-- (12.16 secs, 30,378,380,552 bytes)

-- λ> menorSerieCompuesta2 75

-- (155922,155996)

-- (0.07 secs, 89,813,752 bytes)

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_menorSerieCompuesta :: Integer -> Property

prop_menorSerieCompuesta n =

n > 1 ==> x == y || y == z

where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

-- La comprobación es

-- λ> quickCheck prop_menorSerieCompuesta

-- +++ OK, passed 100 tests.

Referencias

Sucesión A030296 de la OEIS.

2 Comentarios

import Data.Numbers.Primes
import Test.QuickCheck


menorSerieCompuesta :: Integer -> (Integer,Integer)
menorSerieCompuesta n = (m, m+n-1)
  where m = head [ p+1 | (p,q) <- zip primes (tail primes)
                       , p+n < q ]

prop_SerieCompuesta :: Positive Integer -> Property
prop_SerieCompuesta (Positive n) = n > 1 ==> m `elem` [previo, post]
  where m = fst (menorSerieCompuesta n)
        previo = fst (menorSerieCompuesta (n-1))
        post = fst (menorSerieCompuesta (n+1))

import Data.Numbers.Primes

import Test.QuickCheck

menorSerieCompuesta :: Integer -> (Integer,Integer)

menorSerieCompuesta n = (m, m+n-1)

where m = head [ p+1 | (p,q) <- zip primes (tail primes)

, p+n < q ]

prop_SerieCompuesta :: Positive Integer -> Property

prop_SerieCompuesta (Positive n) = n > 1 ==> m `elem` [previo, post]

where m = fst (menorSerieCompuesta n)

previo = fst (menorSerieCompuesta (n-1))

post = fst (menorSerieCompuesta (n+1))

Responder

import Data.Numbers.Primes
import Data.List

menorSerieCompuesta :: Integer -> (Integer,Integer)
menorSerieCompuesta n = (head xs, last xs)
  where xs = serieCompuesta n
                    
serieCompuesta :: Integer -> [Integer]
serieCompuesta n = reverse (auxSerieCompuesta n [] 1)

auxSerieCompuesta :: Integer -> [Integer] -> Integer -> [Integer]
auxSerieCompuesta 0 xs _  = xs
auxSerieCompuesta n xs m
  | not (isPrime m) = auxSerieCompuesta (n-1) (m:xs) (m+1)
  | otherwise       = auxSerieCompuesta (n+genericLength xs) [] (m+1)

import Data.Numbers.Primes

import Data.List

menorSerieCompuesta :: Integer -> (Integer,Integer)

menorSerieCompuesta n = (head xs, last xs)

where xs = serieCompuesta n

serieCompuesta :: Integer -> [Integer]

serieCompuesta n = reverse (auxSerieCompuesta n [] 1)

auxSerieCompuesta :: Integer -> [Integer] -> Integer -> [Integer]

auxSerieCompuesta 0 xs _ = xs

auxSerieCompuesta n xs m

| not (isPrime m) = auxSerieCompuesta (n-1) (m:xs) (m+1)

| otherwise = auxSerieCompuesta (n+genericLength xs) [] (m+1)

Responder

Números consecutivos compuestos

Soluciones

Referencias

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Referencias

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico