Menu Close

Menor contenedor de primos

El n-ésimo menor contenenedor de primos es el menor número que contiene como subcadenas los primeros n primos. Por ejemplo, el 6º menor contenedor de primos es 113257 ya que es el menor que contiene como subcadenas los 6 primeros primos (2, 3, 5, 7, 11 y 13).

Definir la función

   menorContenedor :: Int -> Int

tal que (menorContenedor n) es el n-ésimo menor contenenedor de primos. Por ejemplo,

   menorContenedor 1  ==  2
   menorContenedor 2  ==  23
   menorContenedor 3  ==  235
   menorContenedor 4  ==  2357
   menorContenedor 5  ==  112357
   menorContenedor 6  ==  113257

Soluciones

import Data.List           (isInfixOf)
import Data.Numbers.Primes (primes)
 
-- 1ª solución
-- ===========
 
menorContenedor :: Int -> Int
menorContenedor n =
  head [x | x <- [2..]
          , and [contenido y x | y <- take n primes]]
 
contenido :: Int -> Int -> Bool
contenido x y =
  show x `isInfixOf` show y
 
-- 2ª solución
-- ===========
 
menorContenedor2 :: Int -> Int
menorContenedor2 n =
  head [x | x <- [2..]
          , all (`contenido` x) (take n primes)]

Pensamiento

¡Ya hay hombres activos!
Soñaba la charca
con sus mosquitos.

Antonio Machado

2 soluciones de “Menor contenedor de primos

  1. frahidzam
    import Data.Numbers.Primes (primes)
    import Data.List (inits)
     
    menorContenedor :: Int -> Int
    menorContenedor n = head [x | x <- [1..], menorContenedorAux x n]
     
    menorContenedorAux :: Int -> Int -> Bool
    menorContenedorAux n a =
      and [ elem x (map listaDeIntToInt (subcadenas (digitosInt n)))
          | x <- take a primes]
     
    digitosInt :: Int -> [Int]
    digitosInt n = [read [x] | x <- show n]
     
    subcadenas :: [Int] -> [[Int]]
    subcadenas []     = []
    subcadenas (x:xs) = [x:y | y <- inits xs] ++ subcadenas xs
     
    listaDeIntToInt :: [Int] -> Int
    listaDeIntToInt xs =
      sum [a*(10^b) | (a,b) <- zip (reverse (separaCifras xs)) [0..]]
     
    separaCifras :: [Int] -> [Int]
    separaCifras []     = []
    separaCifras (x:xs) = digitosInt x ++ separaCifras xs
  2. javmarcha1
     
    import Data.Numbers.Primes (primes, isPrime)
     
    -- 1º DEFINICIÓN (poco  eficiente)
     
     
    menorContenedor :: Int -> Int
    menorContenedor 0 = 1
    menorContenedor x = head [fromIntegral  n | n <- [2..] ,
                               and [ elem y (contiene n) | y <- (take x primes)]]
     
    contiene :: Integer -> [Integer]
    contiene x = [ y | y <- (agrupa x) , isPrime y == True]
     
    agrupa :: Integer -> [Integer]
    agrupa x = [ joiner ys | ys <- (agrupalist x)]
     
    agrupalist :: Integer -> [[Integer]]
    agrupalist x = [ xs | xs <- agrupalist2 [1..(length (show x))] x]
     
    agrupalist2 :: [Int] -> Integer -> [[Integer]]
    agrupalist2 [] _ = []
    agrupalist2 (x:xs) n = agrupaR x (digitos n) ++ agrupalist2 xs n
     
    digitos :: Integer -> [Integer]
    digitos n = [read [x] | x <- show n]
     
    agrupaR :: Int -> [a] -> [[a]]
    agrupaR _ [] = []
    agrupaR n xs | n > (length xs) = []
    agrupaR n xs = take n xs : agrupaR n (drop 1 xs) 
     
    joiner :: [Integer] -> Integer
    joiner (x:xs) = read (concat (map show (x:xs)))
     
    --------------------------------------------------------------------------------
     
    -- 2º DEFINICIÓN (más eficiente)
     
    menorContenedor2 :: Int -> Integer
    menorContenedor2 0 = 1
    menorContenedor2 x = (joiner(eliminaigual1
                         (dig (listafinal7 (listafinal2 (take x primes))))))
     
    listafinal7 :: [Integer] -> [Integer]
    listafinal7 xs | listafinal5 xs == [] = xs
                   | otherwise = listafinal7 (listafinal6 xs)
     
    listafinal6 :: [Integer] -> [Integer]
    listafinal6 xs = (take (head (listafinal5 xs) -1 ) xs) ++
                    (drop  (head (listafinal5 xs)) xs)
     
    listafinal5 :: [Integer] -> [Int]
    listafinal5 xs = [ y | (x,y)<- zip (listafinal4 xs) [1..], x > 1]
     
    listafinal4 :: [Integer] -> [Int]
    listafinal4 xs = [ (aparece (show x) (agrupaR (length (show x))
                (show(joiner(eliminaigual1(dig(listafinal (xs)))))))) | x <- xs]
     
    listafinal3 :: [Integer] -> String
    listafinal3 [] = []
    listafinal3 xs = (show(joiner(eliminaigual1(dig(listafinal xs)))))
     
    aparece :: Eq a => [a] -> [[a]] -> Int
    aparece [] _ = 0
    aparece _ [] = 0
    aparece xs (ys:yss) | xs == ys = 1 + aparece xs yss
                        | otherwise = aparece xs yss
     
    listafinal2 :: [Integer] -> [Integer]
    listafinal2 (xs) = reverse(eliminacero(ordena(m(listafinal xs))))                           
    listafinal :: [Integer] -> [Integer]
    listafinal [] = []
    listafinal xs = [ x | x <- xs , (elem (show x) (pertenece4 xs)) == False]
     
    pertenece4 :: [Integer] -> [String]
    pertenece4 [] = []
    pertenece4 xs = pertenece3 xs ++ pertenece3 (drop (length (sacar xs)) xs)
     
    pertenece3 :: [Integer] -> [String]
    pertenece3 [] = []
    pertenece3 xs = [ ys | ys <- lista2 xs, pertenece2 ys (lista xs) /= [] ]
     
    pertenece2 :: String -> [String]  -> String
    pertenece2 _ [] = []
    pertenece2 xs (ys:yss) | xs == ys = xs
                           | otherwise = pertenece2 xs yss
     
    lista :: [Integer] -> [String]
    lista xs | and [(length (show x)) == (length (show (head xs)))  | x <- xs]
              == True = []
             | otherwise = (agrupaR (length(show (head (sacar xs))))
               (show (joiner(drop (length (sacar xs)) xs))))
     
    lista2 :: [Integer] -> [String]
    lista2 (xs) = (agrupaR1 (length(show (head (sacar xs)))) (sacar2 xs))
     
    agrupaR1 :: Int -> [a] -> [[a]]
    agrupaR1 _ [] = []
    agrupaR1 n xs | n > (length xs) = []
    agrupaR1 n xs = take n xs : agrupaR1 n (drop n xs)
     
    sacar2 :: [Integer] -> [Char]
    sacar2 xs = [ a | a <- (show (joiner(sacar (xs))))]
     
    sacar :: [Integer] -> [Integer]
    sacar xs = [ x | x <- xs, length (show x) == length (show (head xs))]
     
    eliminaigual1 :: [Integer] -> [Integer]
    eliminaigual1 xs | eliminaigual2 xs == [] = xs
                     | otherwise = eliminaigual1
                     ((take (head (eliminaigual2 xs) -1 ) xs) ++
                    (drop  (head (eliminaigual2 xs)) xs) )
     
    eliminaigual2 :: [Integer] -> [Int]
    eliminaigual2 xs = [fromIntegral x | x <- igualposicion xs ,
                        elem (x-1) (igualposicion xs)
                        &&  elem (x+1) (igualposicion xs)]
     
    igualposicion :: [Integer] -> [Integer]
    igualposicion xs = [ n | (a,n) <- zip xs [1..] , elem a (tresiguales xs), a==1]
     
    tresiguales :: [Integer] -> [Integer]
    tresiguales xs | length xs < 3 = []
    tresiguales (x:y:z:xs) | x==y && y==z = x : tresiguales (y:z:xs)
                               | otherwise =  tresiguales (y:z:xs)    
     
     
    dig :: [Integer] -> [Integer]
    dig xs = digitos (joiner(eliminacero(ordena( m xs))))
     
     
    eliminacero :: [Integer] -> [Integer]
    eliminacero [] = []
    eliminacero (x:xs) | rem x 10 /= 0 = x : eliminacero xs
                       | otherwise = eliminacero ((div x 10):xs)
     
    ordena :: Ord a => [a] -> [a]
    ordena [] = []
    ordena (x:xs) =  ordena menores ++ [x] ++ ordena mayores
        where menores = [y | y <- xs, y <= x]
              mayores = [y | y <- xs, y >  x]
     
    l :: [Integer] -> Int
    l xs = length (show (last  xs))
     
    l2 :: [Integer] -> [Int]
    l2 xs = [ (l xs) - (length (show x)) | x <- xs]
     
    m :: [Integer] -> [Integer]
    m xs = [ x*(10^y) |(x,y) <- zip xs (l2 xs)]
     
    -------------------------------------------------------------------------
     
    -- EFICIENCIA:
     
     
    --λ> menorContenedor 6
    --113257
    --(42.52 secs, 32,629,175,072 bytes)
    --λ> menorContenedor2 6
    --113257
    --(0.02 secs, 3,014,392 bytes)
     
    --λ> menorContenedor 30
    --10110310710911317192329414347535961677379838997
    --( ≈ 1.2036108604497068e35 años) 
    --λ> menorContenedor2 30
    --10110310710911317192329414347535961677379838997
    --(4.61 secs, 1,127,487,392 bytes)  
     
     
     
    -- Tengo dudas en el caso menorContenedor 0 ¿0 o 1?

Escribe tu solución

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