Menu Close

Menor x tal que los x múltiplos de n contienen todos los dígitos

Definir la función

   menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

   92                                    contiene  [2,9]
   92 y 92×2                             contienen [1,2,4,8,9]
   92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
   92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

   menorX 92          ==  6
   menorX 2967        ==  3
   menorX 266         ==  4
   menorX 18          ==  5
   menorX 2           ==  45
   menorX 125         ==  72
   menorX 1234567890  ==  1
   maximum [menorX n | n <- [1..3000]]  ==  72
   minimum [menorX n | n <- [1..3000]]  ==  3

Soluciones

import Data.List ((\\))
 
-- 1ª definición
-- =============
 
menorX :: Integer -> Integer
menorX n =
  head [x | x <- [1..]
          , [0..9] `contenido` digitosMultiplos n x]
 
contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys =
  all (`elem` ys) xs
 
digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
  concatMap digitos [n,2*n..x*n]
 
digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]
 
-- 2ª definición
-- =============
 
menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
  where aux xs x
          | [0..9] `contenido` xs = x
          | otherwise             = aux (digitos (n*(x+1)) ++ xs) (x+1)
 
-- 3ª definición
-- =============
 
menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
  where aux xs x
          | null xs   = x
          | otherwise = aux (xs \\ show (n*(x+1))) (x+1)
 
-- 4ª definición
-- =============
 
menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
  where aux xs x nx | null ys   = x
                    | otherwise = aux ys (1+x) (nx+n)
          where ys = xs \\ show nx
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximum [menorX n | n <- [1..6000]]
--    72
--    (2.04 secs, 3,737,579,888 bytes)
--    λ> maximum [menorX2 n | n <- [1..6000]]
--    72
--    (0.52 secs, 818,602,736 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.10 secs, 67,090,800 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.08 secs, 67,090,800 bytes)
--    
--    λ> maximum [menorX3 n | n <- [1..10^5]]
--    72
--    (0.81 secs, 1,044,781,216 bytes)
--    λ> maximum [menorX4 n | n <- [1..10^5]]
--    72
--    (0.71 secs, 1,009,113,304 bytes)
Medio

14 soluciones de “Menor x tal que los x múltiplos de n contienen todos los dígitos

  1. angruicam1
    import Data.List (sort,nub)
    import Data.Maybe (fromJust)
     
    menorX :: Integer -> Integer
    menorX n = toInteger . fromJust $ lookup “0123456789” [(sort . nub . concat . map show . take m $ iterate (+n) n,m) | m <- [1..]]
    • anddonram

      Me has servido de inspiración para poder hacerlo.
      Solo un comentario, probablemente lookup sea O(n) ya que es una lista y no un diccionario. length también es O(n) y ya que tiene que contener los 10 elementos distintos (por nub), podemos aprovecharnos de eso y ahorrarnos el sort.

      import Data.List
      import Data.Maybe
      menorX :: Integer -> Integer
      menorX n= fromMaybe 0 $ find (x-> (length $ nub $ concat (map show [n,2*n..x*n]) ) == 10) [1..]
  2. jaibengue
    import Data.List (sort)
     
    menorX :: Integer -> Integer
    menorX n = aux 1 []
      where aux m xs | xs == ['0'..'9'] = (m-1)
                     | otherwise        = aux (m+1) (aux2 (show (m*n)) xs)
              where aux2 [] xs                   = sort xs
                    aux2 (y:ys) xs | y `elem` xs = aux2 ys xs
                                   | otherwise   = aux2 ys (y:xs)
  3. pabhueacu
    menorX :: Integer -> Integer
    menorX x = contiene [] x 1
     
    contiene :: [Char] -> Integer -> Integer -> Integer
    contiene xs n y | length xs == 10 = y-1
                    | otherwise = contiene (sort.nub $ xs ++ show (n*y)) n (y+1)
    • jaibengue

      Buena definición, mejor si le quitas el sort que no lo necesitas y lo metes como función auxiliar de menorX para no cargar con la variable n en el argumento.

      import Data.List(nub)
       
      menorX :: Integer -> Integer
      menorX x = contiene [] 1
        where contiene xs y | length xs == 10 = y-1
                            | otherwise       = contiene (nub $ xs ++ show (x*y)) (y+1)
  4. jorcatote
     
    menorX :: Integer -> Integer
    menorX = aux "0123456789" [1..]
     
    aux :: String -> [Integer] -> Integer -> Integer
    aux xs ys n | m == []   = 1
                | otherwise = 1 + aux m (tail ys) n
                   where m = filter (`notElem` (show (n* head ys))) xs

    Creo que es algo más eficiente que el resto.

    • angruicam1

      Buenas, puedes hacer tu función aún más eficiente si tomas ys como (y:ys) y así te ahorras el usar head y tail. También puedes usar la función (\\) de Data.List para hacer más eficiente el cálculo de m. Quedaría tal que así:

      import Data.List (())
       
      menorX :: Integer -> Integer
      menorX = aux "0123456789" [1..]
       where aux :: String -> [Integer] -> Integer -> Integer
             aux xs (y:ys) n | m == []   = 1
                             | otherwise = 1 + aux m ys n
               where m = xs  show (n*y)
       
      -- Comparación de la eficiencia:
      -- λ> maximum [menorX n | n <- [1..4000000]]
      -- 72
      -- (56.42 secs, 34,850,866,600 bytes)
      -- λ> maximum [menorX2 n | n <- [1..4000000]]
      -- 72
      -- (90.64 secs, 24,395,032,848 bytes)

      Donde menorX2 es tu función.

      • jaibengue

        Muy buena!
        Estaba pensando que quizá se podría mejorar la eficiencia de esta manera:

        import Data.List ((\))
         
        menorX :: Integer -> Integer
        menorX n = aux "0123456789" n
         where aux :: String -> Integer -> Integer
               aux xs u | m == []   = 1
                        | otherwise = 1 + aux m (u+n)
                 where m = xs \ show u

        Dejando así la lista infinita [1..] fuera de la definición y en lugar de hacer el producto (n*y) cada vez que simplemente sumara n al anterior.
        Sin embargo esta mejora no resulta eficiente ya que solo se usa el producto hasta 72*n como mucho, y calcular tan pocos productos y tan pequeños no le resulta costoso al ordenador.

  5. carriomon1
    import Data.List
    import Data.Char
     
    menorX :: Integer -> Integer
    menorX x = head [toInteger n | n <- [1..], listaDigitos (take n (multiplos x)) == 0123456789] 
     
    multiplos :: Integer -> [Integer]
    multiplos n = [n*b | b <- [1..]]
     
    listaDigitos :: [Integer] -> Integer
    listaDigitos xs = read $ nub(sort(concat(map (show) xs)))
  6. alvblamol
    menorX :: Integer -> Integer
    menorX n =
      fromIntegral (head [x | x <-[0..]
                            , contieneTodosDigitos (digitosLista (take x (multiplos n)))])
     
    multiplos n = [n*x | x <- [1..]]
     
    digitos n | n < 10    = [n]
                | otherwise = (mod n 10) : (digitos (div n 10))
     
    digitosLista [] = []
    digitosLista (x:xs) = (digitos x) ++ digitosLista xs
     
    contieneTodosDigitos xs = and [elem x xs | x <- [1..9]]
  7. agumaragu1
     
    menorX :: Integer -> Integer
    menorX n = aux n 1 []
      where aux n m s | check s    = m-1
                      | otherwise  = aux n (m+1) (show(n*m)++s)
     
    check :: [Char] -> Bool
    check st = all (`elem` st) "0123456789"

Escribe tu solución

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