Sucesión de mcd de consecutivos
El enunciado de un 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
sucesionA :: [Integer] sucesionB :: [Integer]
tales que
- los elementos de sucesionA son los términos de la sucesión a(n). Por ejemplo,
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,
sucesionB !! 0 == 1 sucesionB !! 4 == 7 sucesionB !! (10^9) == 1
Usando sucesionB, conjeturar la respuesta del problema y comprobarla con QuickCheck.
Soluciones
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 = [1,1,1,1] ++ cycle (7 : replicate 6 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.