Menu Close

Día: 23 abril, 2021

Mayores potencias de 5 que dividen a la sucesión (OME2014 P4)

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 2014 es

Sea {x(n)} la sucesión de enteros positivos definida por x(1) = 2 y x(n+1) = 2*x(n)^3+x(n) para todo n >= 1. Determinar la mayor potencia de 5 que divide al número x(2014)^2+1.

Definir la función

   mayorExponente :: Integer -> Integer

tal que (mayorExponente n) es el mayor m tal que 5^m divide al número x(n)^2+1.

Soluciones

-- 1ª solución
-- ===========
 
mayorExponente :: Integer -> Integer
mayorExponente n =
  mayorExponenteDe5QueDivide ((termino n)^2 + 1)
 
-- (termino n) es el término n-ésimo de la sucesión. Por ejemplo,
--    termino 2  ==  18
--    termino 3  ==  11682
--    termino 4  ==  3188464624818
termino :: Integer -> Integer
termino 1 = 2
termino n = 2*x^3+x
  where x = termino (n-1)
 
-- (mayorExponenteDe5QueDivide n) es el mayor exponente de 5 que divide a n. Por
-- ejemplo,
--    mayorExponenteDe5QueDivide 50  ==  2
mayorExponenteDe5QueDivide :: Integer -> Integer
mayorExponenteDe5QueDivide n
  | n `mod` 5 /= 0 = 0
  | otherwise      = 1 + mayorExponenteDe5QueDivide (n `div` 5)
 
-- 2ª solución
-- ===========
 
-- Con el siguente cálculo
--    λ> [mayorExponente n | n <- [1..5]]
--    [1,2,3,4,5]
-- se observa que el mayor exponente de 5 que divide a x(n)^2+1 es n.
 
mayorExponente2 :: Integer -> Integer
mayorExponente2 = id

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>