Sucesiones conteniendo al producto de consecutivos
El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1984 es
Sea c un entero positivo. La sucesión f(n) está definida por
f(1) = 1, f(2) = c, f(n+1) = 2f(n) - f(n-1) + 2 (n ≥ 2).
Demostrar que para cada k ∈ N exist un r ∈ N tal que f(k)f(k+1) = f(r).
Definir la función
sucesion :: Integer -> [Integer]
tal que los elementos de (sucesion c) son los términos de la suceción f(n) definida en el enunciado del problema. Por ejemplo,
take 7 (sucesion 2) == [1,2,5,10,17,26,37] take 7 (sucesion 3) == [1,3,7,13,21,31,43] take 7 (sucesion 4) == [1,4,9,16,25,36,49] sucesion 2 !! 30 == 901 sucesion 3 !! 30 == 931 sucesion 4 !! 30 == 961 sucesion 2 !! (10^2) == 10001 sucesion 2 !! (10^3) == 1000001 sucesion 2 !! (10^4) == 100000001 sucesion 2 !! (10^5) == 10000000001 sucesion 2 !! (10^6) == 1000000000001 sucesion 2 !! (10^7) == 100000000000001 sucesion 3 !! (10^7) == 100000010000001 sucesion 4 !! (10^7) == 100000020000001 sucesion 2 !! (10^8) == 10000000000000001 sucesion 3 !! (10^8) == 10000000100000001 sucesion 4 !! (10^8) == 10000000200000001 sucesion 2 !! (10^9) == 1000000000000000001
Comprobar con QuickCheck que para cada k ∈ N existe un r ∈ N tal que f(k)f(k+1) = f(r).
Soluciones
import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª solución -- =========== sucesion :: Integer -> [Integer] sucesion c = map (termino c) [1..] termino :: Integer -> Integer -> Integer termino c 1 = 1 termino c 2 = c termino c n = 2 * termino c (n-1) - termino c (n-2) + 2 -- 2ª solución -- =========== sucesion2 :: Integer -> [Integer] sucesion2 c = 1 : c : [2*y-x+2 | (x,y) <- zip (sucesion3 c) (tail (sucesion3 c))] -- 2ª solución -- =========== sucesion3 :: Integer -> [Integer] sucesion3 c = map (termino3 c) [1..] termino3 :: Integer -> Integer -> Integer termino3 c 1 = 1 termino3 c 2 = c termino3 c n = n^2 + b*n - b where b = c - 4 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucesion 2 !! 32 -- 1025 -- (3.95 secs, 1,991,299,256 bytes) -- λ> sucesion2 2 !! 32 -- 1025 -- (0.01 secs, 119,856 bytes) -- λ> sucesion3 2 !! 32 -- 1025 -- (0.01 secs, 111,176 bytes) -- -- λ> sucesion2 2 !! (10^7) -- 100000000000001 -- (2.26 secs, 5,200,111,128 bytes) -- λ> sucesion3 2 !! (10^7) -- 100000000000001 -- (0.27 secs, 1,600,111,568 bytes) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equivalencia :: Integer -> Int -> Property prop_equivalencia c k = c > 0 && k >= 0 ==> take 20 (sucesion c) == take 20 (sucesion2 c) && sucesion2 c !! k == sucesion3 c !! k -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Propiedad -- ========= -- La propiedad es prop_sucesion :: Integer -> Int -> Property prop_sucesion c k = c > 0 && k >= 0 ==> (ys !! k) `elem` xs where xs = sucesion2 c ys = zipWith (*) xs (tail xs) -- La comprobación es -- λ> quickCheck prop_sucesion -- +++ OK, passed 100 tests.