Diferencias de potencias congruentes con 5 módulo 7
El enunciado de un problema 5 de la Fase Local de la Olimpiada Matemática Española del 2012 es
Consideremos el número entero positivo , donde r y s son también enteros positivos. Hallar las condiciones que deben cumplir r y s para que el resto de la división de n por 7 sea 5. Hallar el menor número que cumple esta condición.
Definir la lista
1 |
exponentes :: [(Integer,Integer)] |
tal que sus elementos son los pares de enteros positivos (r,s) tales que es un número entero positivo cuyo resto al dividirlo por 7 es 5. Por ejemplo,
1 2 3 |
head exponentes == (10,2) exponentes !! 23 == (43,8) exponentes !! (10^7) == (26836,1826) |
Usando la función exponentes, calcular la respuesta a la pregunta del problema; es decir, hallar el menor número que cumple la condició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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª solución -- =========== exponentes :: [(Integer,Integer)] exponentes = [(r,s) | (r,s) <- pares, let n = 2^r - 16^s, n > 0, n `mod` 7 == 5] -- pares el lista de pares de enteros positivos con el primero mayor que -- el segundo. Por ejemplo, -- λ> take 10 pares -- [(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4)] pares :: [(Integer,Integer)] pares = [(a,b) | a <- [1..] , b <- [1..a-1]] -- 2ª solución -- =========== -- Observando los siguientes cálculos -- λ> take 28 exponentes -- [(10,2),(13,2),(16,2),(19,2),(22,2),(22,5),(25,2),(25,5),(28,2), -- (28,5),(31,2),(31,5),(34,2),(34,5),(34,8),(37,2),(37,5),(37,8), -- (40,2),(40,5),(40,8),(43,2),(43,5),(43,8),(46,2),(46,5),(46,8), -- (46,11)] -- λ> [((x-1) `div` 3, (y-2) `div` 3) | (x,y) <- it] -- [(3,0),(4,0),(5,0),(6,0),(7,0),(7,1),(8,0),(8,1),(9,0),(9,1), -- (10,0),(10,1),(11,0),(11,1),(11,2),(12,0),(12,1),(12,2),(13,0), -- (13,1),(13,2),(14,0),(14,1),(14,2),(15,0),(15,1),(15,2),(15,3)] exponentes2 :: [(Integer,Integer)] exponentes2 = concat [[(r,s) | s <- takeWhile (<= (r `div` 4)) ys] | r <- xs] where xs = [10,13..] ys = [2,5..] -- 3ª solución -- =========== exponentes3 :: [(Integer,Integer)] exponentes3 = [(r,s) | r <- [1,4..], s <- [2,5..r `div` 4]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_exponentes :: Int -> Property prop_exponentes n = n >= 0 ==> all (== (exponentes !! n)) [exponentes2 !! n, exponentes3 !! n] -- La comprobación es -- λ> quickCheck prop_exponentes -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> exponentes !! (3*10^4) -- (1471,332) -- (5.21 secs, 7,844,582,216 bytes) -- λ> exponentes2 !! (3*10^4) -- (1471,332) -- (0.04 secs, 6,551,432 bytes) -- λ> exponentes3 !! (3*10^4) -- (1471,332) -- (0.01 secs, 5,512,056 bytes) -- -- λ> exponentes2 !! (10^7) -- (26836,1826) -- (3.25 secs, 2,083,815,616 bytes) -- λ> exponentes3 !! (10^7) -- (26836,1826) -- (2.57 secs, 1,757,467,216 bytes) -- Cálculo de la respuesta -- ======================= -- El cálculo es -- λ> (r,s) = head exponentes -- λ> 2^r - 16^s -- 768 -- Por tanto, el número pedido es el 768. |
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>
Puede ser divertido establecer una biyección para obtener directamente cualquier tupla: