{"id":6386,"date":"2021-05-13T06:00:58","date_gmt":"2021-05-13T04:00:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6386"},"modified":"2021-05-20T08:12:39","modified_gmt":"2021-05-20T06:12:39","slug":"sucesion-de-mcd-de-consecutivos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sucesion-de-mcd-de-consecutivos\/","title":{"rendered":"Sucesi\u00f3n de mcd de consecutivos"},"content":{"rendered":"

El enunciado del problema B3 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2007<\/a> es<\/p>\n

\n Sea a(n) = 1 + n\u00b3 la sucesi\u00f3n {2,9,28,65,…} y b(n) = mcd(a(n),a(n+1)). Hallar el m\u00e1ximo valor que puede tomar b(n).\n<\/p><\/blockquote>\n

Definir las listas<\/p>\n

\n   sucesionA :: [Integer]\n   sucesionB :: [Integer]\n<\/pre>\n
tales que<\/p>\n
    \n
  • los elementos de sucesionA son los t\u00e9rminos de la sucesi\u00f3n a(n). Por ejemplo,<\/li>\n<\/ul>\n
    \n     take 12 sucesionA  ==  [2,9,28,65,126,217,344,513,730,1001,1332,1729]\n<\/pre>\n
      \n
    • los elementos de sucesionAB son los t\u00e9rminos de la sucesi\u00f3n b(n). Por ejemplo,<\/li>\n<\/ul>\n
      \n   sucesionB !! 0       ==  1\n   sucesionB !! 4       ==  7\n   sucesionB !! (10^9)  ==  1\n<\/pre>\n
      Usando sucesionB, conjeturar la respuesta del problema y comprobarla con QuickCheck.<\/p>\n
      Soluciones<\/h4>\n
      \nimport Data.List (cycle)\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\nsucesionA :: [Integer]\nsucesionA = [1+n^3 | n <- [1..]]\n\n-- 1\u00aa definici\u00f3n de sucesionB\n-- ==========================\n\nsucesionB :: [Integer]\nsucesionB =\n  zipWith gcd sucesionA (tail sucesionA)\n\n-- 2\u00aa definici\u00f3n de sucesionB\n-- ==========================\n\n-- Observando  los siguientes c\u00e1lculos\n--    \u03bb> take 30 sucesionB\n--    [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]\n--    \u03bb> take 10 [n | (n,x) <- zip [1..] sucesionB, x == 7]\n--    [5,12,19,26,33,40,47,54,61,68]\n\nsucesionB2 :: [Integer]\nsucesionB2 = cycle [1,1,1,1,7,1,1]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sucesionB :: Int -> Property\nprop_sucesionB n =\n  n >= 0 ==>\n  sucesionB !! n == sucesionB2 !! n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sucesionB\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sucesionB !! (10^7)\n--    1\n--    (5.23 secs, 2,880,105,504 bytes)\n--    \u03bb> sucesionB2 !! (10^7)\n--    1\n--    (0.06 secs, 98,600 bytes)\n\n-- C\u00e1lculo de la respuesta\n-- =======================\n\n-- Observando los c\u00e1lculos\n--    \u03bb> take 30 sucesionB\n--    [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]\n--    \u03bb> take 30 ([1,1,1,1] ++ cycle (7 : replicate 6 1))\n--    [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]\n--    \u03bb> take 100 sucesionB == take 100 ([1,1,1,1] ++ cycle (7 : replicate 6 1))\n--    True\n-- La conjetura es que el m\u00e1ximo es 7. Su expresi\u00f3n es\n\nprop_maximo :: Int -> Property\nprop_maximo n =\n  n > 4 ==>\n  maximum (take n sucesionB) == 7\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maximo\n--    +++ OK, passed 100 tests.\n<\/pre>\n
      Nuevas soluciones<\/h4>\n
        \n
      • En los comentarios se pueden escribir nuevas soluciones.\n
      • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
        El enunciado del problema B3 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2007 es Sea a(n) = 1 + n\u00b3 la sucesi\u00f3n {2,9,28,65,…} y b(n) = mcd(a(n),a(n+1)). Hallar el m\u00e1ximo valor que puede tomar b(n). Definir las listas sucesionA :: [Integer] sucesionB :: [Integer] tales que los elementos de sucesionA son los…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6386"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6386"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6386\/revisions"}],"predecessor-version":[{"id":6474,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6386\/revisions\/6474"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6386"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6386"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6386"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}