Menu Close

Múltiplos repitunos (OME1993 P4)

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1993 es

Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111……1 (escrito sólo con unos).

Definir la función

   multiplosRepitunos :: Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111…1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

   take 2 (multiplosRepitunos 7) == [111111,111111111111]
   head (multiplosRepitunos 19)  == 111111111111111111
   length (show (head (multiplosRepitunos (primes !! (10^5))))) == 43324

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
multiplosRepitunos :: Integer -> [Integer]
multiplosRepitunos p =
  [x | x <- repitunos
     , mod x p == 0]
 
-- repitunos es la lista de los números de la forma 111...1 (escrito sólo con
-- unos). Por ejemplo,
--    take 5 repitunos  ==  [1,11,111,1111,11111]
repitunos :: [Integer]
repitunos = 1 : [10*x+1 | x <- repitunos]
 
-- 2ª solución
-- ===========
 
multiplosRepitunos2 :: Integer -> [Integer]
multiplosRepitunos2 p =
  [x | x <- repitunos2
     , mod x p == 0]
 
repitunos2 :: [Integer]
repitunos2 = [div (10^n-1) 9 | n <- [1..]]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (show (head (multiplosRepitunos (primes !! (10^5)))))
--    43324
--    (0.58 secs, 1,272,561,448 bytes)
--    λ> length (show (head (multiplosRepitunos2 (primes !! (10^5)))))
--    43324
--    (5.50 secs, 2,563,458,656 bytes)
 
-- Comprobación
-- ============
 
-- La propiedad es
prop_multiplosRepitunos :: Int -> Property
prop_multiplosRepitunos k =
  k > 2  ==>
  not (null (multiplosRepitunos (primes !! k)))
 
-- La comprobación es
--    λ> quickCheck prop_multiplosRepitunos
--    +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

3 soluciones de “Múltiplos repitunos (OME1993 P4)

  1. Joaquín Infante Rodríguez
    import Data.List
    import Data.Numbers.Primes
     
    listaNumero :: [Integer] -> Integer
    listaNumero [] = 0
    listaNumero (x:xs) = x*10^(genericLength (x:xs)-1) + listaNumero xs
     
    multiplosRepitunos :: Integer -> [Integer]
    multiplosRepitunos p | not (isPrime p) || p==2 || p==5 = error "el numero introducido no es valido"
                         | otherwise = [listaNumero (genericReplicate k 1) | k<-[listaNumero (replicate n 1)..],
                                        rem (listaNumero (genericReplicate k 1)) p == 0]
                                       where n = genericLength (show p)
     
     
    prop :: Integer -> Integer -> Property
    prop p n = n>0 && (isPrime p) && p>5 ==> head (dropWhile (<=n) (multiplosRepitunos p)) > n
     
    -- quickCheck prop
    -- *** Gave up! Passed only 44 tests.
    -- (0.01 secs, 18,446,392 bytes)
  2. Rubén Muñoz Mkrtchian
    -- Definición:
    -- ==========
     
    multiplosRepitunos :: Integer -> [Integer]
    multiplosRepitunos p = [n | n <- listaUnos, mod n p == 0]
     
    -- listaUnos es una lista de enteros tal que el n-ésimo término es un número
    -- formado por n unos. Por ejemplo,
    --    λ> take 10 listaUnos
    --    [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111]
     
    listaUnos :: [Integer]
    listaUnos = scanl1 (+) (map (10^) [0..])
     
    -- Propiedad:
    -- =========
     
    prop :: Integer -> Integer -> Bool
    prop p n = not (isPrime p') || not (null (filter (>n) (multiplosRepitunos p')))
      where p' = abs p + 6
     
    -- La comprobación es:
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
  3. j0sejuan
    {-
     
      Sabiendo que el resto de 1111.....11 `div` p == 0
     
      Podemos "deshacer" la división (algoritmo tradicional antes
      del desastroso método del ABN) y los resíduos se relacionan
      como:
     
        r{i} = 10 r{i+1} + 1 - p d{i}
     
      (siendo d{i} el dígito que corresponde en la división al
      resto del paso {i}).
     
      Además, es obvio que sólo hay un dígito d{i} posible.
     
      Por tanto todos resíduos "deshaciendo" la división del cole
      son:
     
    -}
    reps :: Integer {- prime -} -> [(Integer {- resto -}, Int {- nº de unos -})]
    reps p = iterate rec (0, 0)
      where rec (r, s) = head [ (r', s + 1)
                              | d <- [0..9]
                              , let (r', w) = (r + p * d - 1) `divMod` 10
                              , w == 0 ]
     
    -- y los divisores serán aquellos cuyo resto esté formado por unos
    multiplosRepitunos :: Integer -> [Integer]
    multiplosRepitunos p = [ read (rr ++ take s (repeat '1'))
                           | (r, s) <- reps p
                           , let rr = show r
                           , nub rr == "1"]
     
    {-
     
    *Main> (length . show . head . multiplosRepitunos) (primes!!(10^5))
    43324
    (0.64 secs, 692,423,320 bytes)
     
    *Main> (length . show . head . multiplosRepitunos) (primes!!(10^6))
    7742933
    (71.69 secs, 39,323,238,576 bytes)
     
    -}

Leave a Reply

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