Menu Close

Menor contenedor de primos

José A. Alonso,

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

Posted in Avanzado
Tagged , , , , , , ,

2 Comments

  1. frahidzam
    Responder 
    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
    Responder 
     
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.