Sucesión de mcd de consecutivos
El enunciado del problema B3 de la Fase Local de la Olimpiada Matemática Española del 2007 es
Sea a(n) = 1 + n³ la sucesión {2,9,28,65,…} y b(n) = mcd(a(n),a(n+1)). Hallar el máximo valor que puede tomar b(n).
Definir las listas
1 2 |
sucesionA :: [Integer] sucesionB :: [Integer] |
tales que
- los elementos de sucesionA son los términos de la sucesión a(n). Por ejemplo,
1 |
take 12 sucesionA == [2,9,28,65,126,217,344,513,730,1001,1332,1729] |
- los elementos de sucesionAB son los términos de la sucesión b(n). Por ejemplo,
1 2 3 |
sucesionB !! 0 == 1 sucesionB !! 4 == 7 sucesionB !! (10^9) == 1 |
Usando sucesionB, conjeturar la respuesta del problema y comprobarla con QuickCheck.
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 |
import Data.List (cycle) import Test.QuickCheck (Property, (==>), quickCheck) sucesionA :: [Integer] sucesionA = [1+n^3 | n <- [1..]] -- 1ª definición de sucesionB -- ========================== sucesionB :: [Integer] sucesionB = zipWith gcd sucesionA (tail sucesionA) -- 2ª definición de sucesionB -- ========================== -- Observando los siguientes cálculos -- λ> take 30 sucesionB -- [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1] -- λ> take 10 [n | (n,x) <- zip [1..] sucesionB, x == 7] -- [5,12,19,26,33,40,47,54,61,68] sucesionB2 :: [Integer] sucesionB2 = cycle [1,1,1,1,7,1,1] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sucesionB :: Int -> Property prop_sucesionB n = n >= 0 ==> sucesionB !! n == sucesionB2 !! n -- La comprobación es -- λ> quickCheck prop_sucesionB -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucesionB !! (10^7) -- 1 -- (5.23 secs, 2,880,105,504 bytes) -- λ> sucesionB2 !! (10^7) -- 1 -- (0.06 secs, 98,600 bytes) -- Cálculo de la respuesta -- ======================= -- Observando los cálculos -- λ> take 30 sucesionB -- [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1] -- λ> take 30 ([1,1,1,1] ++ cycle (7 : replicate 6 1)) -- [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1] -- λ> take 100 sucesionB == take 100 ([1,1,1,1] ++ cycle (7 : replicate 6 1)) -- True -- La conjetura es que el máximo es 7. Su expresión es prop_maximo :: Int -> Property prop_maximo n = n > 4 ==> maximum (take n sucesionB) == 7 -- La comprobación es -- λ> quickCheck prop_maximo -- +++ 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>
2 Comentarios