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
1 |
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,
1 2 3 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
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>