{"id":1446,"date":"2015-05-12T06:00:20","date_gmt":"2015-05-12T04:00:20","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1446"},"modified":"2015-06-13T16:34:03","modified_gmt":"2015-06-13T14:34:03","slug":"el-teorema-de-midy","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-teorema-de-midy\/","title":{"rendered":"El teorema de Midy"},"content":{"rendered":"<p>El ejercicio de hoy, propuesto por Antonio Garc\u00eda Bl\u00e1zquez, tiene como objetivo comprobar la veracidad del <a href=\"http:\/\/bit.ly\/1PwNqz4\">Teorema de Midy<\/a>, este teorema dice:<\/p>\n<blockquote><p>\n  Sea a\/p una fracci\u00f3n, donde a &lt; p y p > 5 es un n\u00famero primo. Si esta fracci\u00f3n tiene una expansi\u00f3n decimal peri\u00f3dica, donde la cantidad de d\u00edgitos en el per\u00edodo es par, entonces podemos partir el per\u00edodo en dos mitades, cuya suma es un n\u00famero formado \u00fanicamente por nueves.<\/p>\n<p>  Por ejemplo, 2\/7 = 0&#8217;285714285714&#8230; El per\u00edodo es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.\n<\/p><\/blockquote>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   teoremaMidy :: Integer -> Bool\n<\/pre>\n<p>tal que (teoremaMidy n) se verifica si para todo todo n\u00famero primo p menor que n y mayor que 5 y todo n\u00famero natural a menor que p tales que la cantidad de d\u00edgitos en el per\u00edodo de a\/p es par, entonces podemos partir el per\u00edodo de a\/p en dos mitades, cuya suma es un n\u00famero formado \u00fanicamente por nueves. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   teoremaMidy 200  ==  True\n<\/pre>\n<p>Adem\u00e1s, comprobar el teorema de Midy usando QuickCheck.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericTake)\nimport Data.Numbers.Primes (primes, isPrime)\nimport Test.QuickCheck\n\nteoremaMidy :: Integer -> Bool\nteoremaMidy n = \n    all conclusionMidy [(a,p) | p <- takeWhile (<n) (drop 3 primes),\n                                a <- [1..p-1],\n                                tienePeriodoDeLongitudPar (a,p)]\n\n-- (tienePeriodoDeLongitudPar (a,p)) se verifica si el per\u00edodo de a\/p\n-- (con p un primo mayor que 5 y que a) es de longitud par. Por ejemplo,  \n--    tienePeriodoDeLongitudPar (1,7)   ==  True\n--    tienePeriodoDeLongitudPar (1,37)  ==  False\ntienePeriodoDeLongitudPar :: (Integer,Integer) -> Bool\ntienePeriodoDeLongitudPar (a,p) =\n    even (longitudPeriodo p)\n\n-- (expansionDec (a,p)) es la expansi\u00f3n decimal de a\/p. Por ejemplo, \n--    take 10 (expansionDec (1,4))    ==  [0,2,5]\n--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]\n--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]\n--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]\nexpansionDec :: (Integer,Integer) -> [Integer]\nexpansionDec (x,y) \n    | r == 0    = [q] \n    | otherwise = q : expansionDec (r*10,y)\n    where (q,r) = quotRem x y\n\n-- (longitudPeriodo p) es la longitud del per\u00edodo de 1\/p (y de\n-- cualquier fracci\u00f3n irreducible de denominador p), donde p es un\n-- n\u00famero primo mayor que 5. Por ejemplo, \n--    longitudPeriodo 7   ==  6\n--    longitudPeriodo 37  ==  3\n--    longitudPeriodo 83  ==  41\nlongitudPeriodo :: Integer -> Integer\nlongitudPeriodo p = head [k | k <- [1..], 10^k `mod` p == 1]\n\n-- (periodo (a,p)) es el per\u00edodo de a\/b (para a < p y p > 5 es primo). \n-- Por ejemplo, \n--    periodo (1,7)   ==  [1,4,2,8,5,7]\n--    periodo (2,7)   ==  [2,8,5,7,1,4]\n--    periodo (6,7)   ==  [8,5,7,1,4,2]\n--    periodo (1,73)  ==  [0,1,3,6,9,8,6,3]\nperiodo :: (Integer,Integer) -> [Integer]\nperiodo (a,p) = genericTake t xs\n    where (_:xs) = expansionDec (a,p)\n          t      = longitudPeriodo p\n\n-- (conclusionMidy (a,p)) se verifica si a\/p verifica la conclusi\u00f3n del\n-- teorema de Midy; es decir, podemos partir el per\u00edodo de a\/p en dos\n-- mitades, cuya suma es un n\u00famero formado \u00fanicamente por nueves. Por\n-- ejemplo,  \n--    conclusionMidy (1,7)   ==  True\n--    conclusionMidy (1,37)  ==  False\nconclusionMidy :: (Integer,Integer) -> Bool\nconclusionMidy (a,p) = \n    all (==9) (zipWith (+) ys zs)\n    where xs      = periodo (a,p)\n          (ys,zs) = splitAt (length xs `div` 2) xs\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Comprobaci\u00f3n con QuickCheck                                      --\n-- ---------------------------------------------------------------------\n\n-- (condicionMidy (a,p)) se verifica si a\/p cumple las condiciones del\n-- teorema de Midy. Por ejemplo,\n--    condicionMidy (1,7)   ==  True\n--    condicionMidy (1,37)  ==  False\ncondicionMidy :: (Integer,Integer) -> Bool\ncondicionMidy (a,p) = \n    a > 0 && \n    a < p &#038;&#038; \n    isPrime p &#038;&#038; \n    p > 5 && \n    tienePeriodoDeLongitudPar (a,p)\n\n-- La propiedad es \nprop_teoremaMidy :: (Integer,Integer) -> Property\nprop_teoremaMidy (a,p) = \n    condicionMidy (a,p) ==> conclusionMidy (a,p)\n\n-- La comprobaci\u00f3n es \n--    ghci> quickCheck prop_teoremaMidy\n--    *** Gave up! Passed only 24 tests.\n\n-- En la comprobaci\u00f3n se observa que la mayor\u00eda de los ejemplos\n-- generados no cumplen la condici\u00f3n del teorema de Midy y s\u00f3lo 24 de\n-- ellos la cumplen y tambi\u00e9n la conclusi\u00f3n. \n\n-- Para aumentar el n\u00famero de casos en lo que se cumpla la condici\u00f3n, se\n-- puede aumentar el valor de maxSuccess; por ejemplo,   \n--    ghci> quickCheckWith (stdArgs {maxSuccess=700}) prop_teoremaMidy\n--    *** Gave up! Passed only 137 tests.\n\n-- Otra forma de conseguirlo es definir un generador de n\u00fameros de Midy\n-- (es decir, de pares (a,p) que cumplan la condici\u00f3n del teorema de\n-- Midy). Por ejemplo, \n--    ghci> sample numeroMidy\n--    (15,19)\n--    (5,7)\n--    (1,23)\n--    (7,11)\nnumeroMidy :: Gen (Integer,Integer)\nnumeroMidy = suchThat arbitrary condicionMidy\n\n-- La propiedad es\nprop_teoremaMidy2 :: Property\nprop_teoremaMidy2 = forAll numeroMidy conclusionMidy\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_teoremaMidy2\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El ejercicio de hoy, propuesto por Antonio Garc\u00eda Bl\u00e1zquez, tiene como objetivo comprobar la veracidad del Teorema de Midy, este teorema dice: Sea a\/p una fracci\u00f3n, donde a &lt; p y p > 5 es un n\u00famero primo. Si esta fracci\u00f3n tiene una expansi\u00f3n decimal peri\u00f3dica, donde la cantidad de d\u00edgitos en el per\u00edodo es&#8230;<\/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":[7],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1446"}],"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=1446"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1446\/revisions"}],"predecessor-version":[{"id":1522,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1446\/revisions\/1522"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}