Últimos dígitos de una sucesión
El enunciado del problema 1 de la Fase Local de la Olimpiada Matemática Española del 2000 es
Considérese la sucesión definida como a(1) = 3, y a(n+1) = a(n) + a(n)². Determínense las dos últimas cifras de a(2000).
Definir las sucesiones
sucesionA :: [Integer] sucesionB :: [Integer]
tales que
- sucesionA es la lista de los términos de la sucesión a(n). Por ejemplo,
take 4 sucesionA == [3,12,156,24492]
- sucesionB es la lista de los dos últimos dígitos de los término de la sucesión a(n). Por ejemplo,
take 4 sucesionB == [3,12,56,92]
sucesionB !! (10^6) == 56
Usando la sucesionB, calcular la respuesta a la pregunta del problema de la Olimpiada.
Soluciones
-- 1ª definición de sucesionA -- ========================== sucesionA :: [Integer] sucesionA = map a [1..] where a 1 = 3 a n = b + b^2 where b = a (n-1) -- 2ª definición de sucesionA -- ========================== sucesionA2 :: [Integer] sucesionA2 = iterate (\x -> x + x^2) 3 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (show (maximum (take 26 sucesionA))) -- 18408940 -- (3.90 secs, 1,213,573,208 bytes) -- λ> length (show (maximum (take 26 sucesionA2))) -- 18408940 -- (3.91 secs, 1,182,719,984 bytes) -- 1ª definición de sucesionB -- ========================== sucesionB :: [Integer] sucesionB = map (`mod` 100) sucesionA -- 2ª definición de sucesionB -- ========================== -- Observando el siguiente cálculo -- λ> take 20 sucesionB -- [3,12,56,92,56,92,56,92,56,92,56,92,56,92,56,92,56,92,56,92] sucesionB2 :: [Integer] sucesionB2 = 3 : 12 : cycle [56,92] -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> take 25 sucesionB == take 25 sucesionB2 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucesionB !! 30 -- 56 -- (10.09 secs, 978,586,056 bytes) -- λ> sucesionB2 !! 30 -- 56 -- (0.01 secs, 98,568 bytes) -- Cálculo de la respuesta -- ======================= -- El cálculo dela respuesta es -- λ> sucesionB2 !! 1999 -- 92 -- Por tanto a(2000) termina en 92.