Menu Close

Día: 21 mayo, 2021

Ú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

[schedule on=’2021-05-28′ at=”06:00″]
-- 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.

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>