Menu Close

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>

2 soluciones de “Sucesión de mcd de consecutivos

  1. Rubén Muñoz Mkrtchian
    -- Definición de sucesionA:
    -- =======================
     
    sucesionA :: [Integer]
    sucesionA = [1+n^3 | n <- [1..]]
     
    -- 1ª Definición de sucesionB:
    -- ==========================
     
    sucesionB :: [Integer]
    sucesionB = zipWith gcd xs (tail xs)
      where xs = sucesionA
     
    -- 2ª Definición de sucesionB:
    -- ==========================
     
    -- En el cálculo de los 50 primeros términos de sucesionB observamos un patrón
    -- claro.
    --    λ> take 50 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,1,1,7,
    --     1,1,1,1,1,1,7,1,1,1,1,1,1,7,1,1,1]
     
    sucesionBOpt :: [Integer]
    sucesionBOpt = cycle [1,1,1,1,7,1,1]
     
    -- A partir de esta definición podemos conjeturar que el máximo valor que puede
    -- tomar b(n) es 7, y lo toma en aquellos n tales que mod n 7 == 5. Vamos a
    -- comprobar efectivamente que el 7 es el máximo valor.
     
    maximoValor :: Int -> Bool
    maximoValor n = maximum (take m sucesionB) == 7
      where m = abs n + 5
     
    -- La comprobación es:
    -- λ> quickCheck maximoValor
    -- +++ OK, passed 100 tests.
     
    -- Equivalencia de las definiciones:
    -- ================================
     
    prop :: Int -> Bool
    prop n = sucesionB !! m == sucesionBOpt !! m
      where m = abs n
     
    -- La comprobación es:
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
     
    -- Comparación de eficiencia:
    -- =========================
    --
    -- λ> sucesionB !! (10^6)
    -- 1
    -- (0.49 secs, 288,059,304 bytes)
    -- λ> sucesionBOpt !! (10^6)
    -- 1
    -- (0.01 secs, 55,960 bytes)
  2. Joaquín Infante Rodríguez
    import Data.List
     
    sucesionA :: [Integer]
    sucesionA = [1+n^3 | n<-[1..]]
     
    sucesionB' :: [Integer]
    sucesionB' = [gcd x y | (x,y)<- zip (sucesionA) (tail sucesionA)]
     
    propMaximo' :: Integer -> Property
    propMaximo' n = n>=5 ==> maximum (genericTake n sucesionB') == 7
     
    --  λ> quickCheck propMaximo'
    --  +++ OK, passed 100 tests.
    --  (0.01 secs, 3,632,560 bytes)
     
    sucesionB :: [Integer]
    sucesionB = [1,1,1,1,7] ++ concat (repeat (((replicate 6 1)++ [7])))
     
    --  λ> sucesionB !! (10^9) == 1
    --     (10.33 secs, 6,056,595,760 bytes)
     
    propSucesionB :: Integer -> Property
    propSucesionB n = n>0 ==> genericTake n sucesionB' == genericTake n sucesionB
     
    --  λ> quickCheck propSucesionB
    --  +++ OK, passed 100 tests.
    --  (0.02 secs, 2,623,440 bytes)
     
    propMaximo :: Integer -> Property
    propMaximo n = n>=5 ==> maximum (genericTake n sucesionB) == 7
     
    --  λ> quickCheck propMaximo
    --  +++ OK, passed 100 tests.
    --  (0.02 secs, 3,586,680 bytes)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.