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
|
1 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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
|
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 |
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. |
En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="haskell"> y otra con </pre>