Múltiplos repitunos
El ejercicio 4 de la Olimpiada Matemáticas de 1993 es el siguiente:
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 -> [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,
head (multiplosRepitunos 7 10) == 111111 head (multiplosRepitunos 7 (10^10)) == 111111111111 head (multiplosRepitunos 7 (10^20)) == 111111111111111111111111 head (multiplosRepitunos 19 (10^10)) == 111111111111111111
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 import Test.QuickCheck -- 1ª solución -- =========== multiplosRepitunos :: Integer -> Integer -> [Integer] multiplosRepitunos p n = [x | x <- dropWhile (<= n) 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 -> [Integer] multiplosRepitunos2 p n = [x | x <- dropWhile (<= n) repitunos2 , mod x p == 0] repitunos2 :: [Integer] repitunos2 = [div (10^n-1) 9 | n <- [1..]] -- Comprobación -- ============ -- La propiedad es prop_multiplosRepitunos :: Int -> Integer -> Property prop_multiplosRepitunos k n = k > 2 && n > 0 ==> not (null (multiplosRepitunos (primes !! k) n)) -- La comprobación es -- λ> quickCheck prop_multiplosRepitunos -- +++ OK, passed 100 tests.