Menu Close

Día: 13 mayo, 2021

Sucesión de mcd de consecutivos

El enunciado del problema B3 de la Fase Local de la Olimpiada Matemática Española del 2007 es

Sea a(n) = 1 + n³ la sucesión {2,9,28,65,…} y b(n) = mcd(a(n),a(n+1)). Hallar el máximo valor que puede tomar b(n).

Definir las listas

   sucesionA :: [Integer]
   sucesionB :: [Integer]

tales que

  • los elementos de sucesionA son los términos de la sucesión a(n). Por ejemplo,
     take 12 sucesionA  ==  [2,9,28,65,126,217,344,513,730,1001,1332,1729]
  • los elementos de sucesionAB son los términos de la sucesión b(n). Por ejemplo,
   sucesionB !! 0       ==  1
   sucesionB !! 4       ==  7
   sucesionB !! (10^9)  ==  1

Usando sucesionB, conjeturar la respuesta del problema y comprobarla con QuickCheck.

Soluciones

import Data.List (cycle)
import Test.QuickCheck (Property, (==>), quickCheck)
 
sucesionA :: [Integer]
sucesionA = [1+n^3 | n <- [1..]]
 
-- 1ª definición de sucesionB
-- ==========================
 
sucesionB :: [Integer]
sucesionB =
  zipWith gcd sucesionA (tail sucesionA)
 
-- 2ª definición de sucesionB
-- ==========================
 
-- Observando  los siguientes cálculos
--    λ> take 30 sucesionB
--    [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1]
--    λ> take 10 [n | (n,x) <- zip [1..] sucesionB, x == 7]
--    [5,12,19,26,33,40,47,54,61,68]
 
sucesionB2 :: [Integer]
sucesionB2 = cycle [1,1,1,1,7,1,1]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_sucesionB :: Int -> Property
prop_sucesionB n =
  n >= 0 ==>
  sucesionB !! n == sucesionB2 !! n
 
-- La comprobación es
--    λ> quickCheck prop_sucesionB
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sucesionB !! (10^7)
--    1
--    (5.23 secs, 2,880,105,504 bytes)
--    λ> sucesionB2 !! (10^7)
--    1
--    (0.06 secs, 98,600 bytes)
 
-- Cálculo de la respuesta
-- =======================
 
-- Observando los cálculos
--    λ> take 30 sucesionB
--    [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1]
--    λ> take 30 ([1,1,1,1] ++ cycle (7 : replicate 6 1))
--    [1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1,1]
--    λ> take 100 sucesionB == take 100 ([1,1,1,1] ++ cycle (7 : replicate 6 1))
--    True
-- La conjetura es que el máximo es 7. Su expresión es
 
prop_maximo :: Int -> Property
prop_maximo n =
  n > 4 ==>
  maximum (take n sucesionB) == 7
 
-- La comprobación es
--    λ> quickCheck prop_maximo
--    +++ OK, passed 100 tests.

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>