Múltiplos repitunos
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.