Menu Close

Día: 5 mayo, 2021

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>