{"id":3965,"date":"2013-12-28T05:47:35","date_gmt":"2013-12-28T04:47:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3965"},"modified":"2016-01-09T18:34:39","modified_gmt":"2016-01-09T17:34:39","slug":"el-desafio-matematico-un-numero-curioso-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-desafio-matematico-un-numero-curioso-en-haskell\/","title":{"rendered":"El desaf\u00edo matem\u00e1tico &#8220;Un n\u00famero curioso&#8221; en Haskell"},"content":{"rendered":"<p>En El Pa\u00eds del d\u00eda 16 se present\u00f3 el desaf\u00edo matem\u00e1tico <a href=\"http:\/\/sociedad.elpais.com\/sociedad\/2013\/12\/16\/videos\/1387208927_861334.html\">Un n\u00famero curios<\/a> cuyo enunciado es el siguiente:<\/p>\n<blockquote><p>\nEl equipo que preparamos los desaf\u00edos matem\u00e1ticos hemos decidido abonarnos durante todo el a\u00f1o a un n\u00famero de la Loter\u00eda. Para elegir ese n\u00famero, que debe estar comprendido entre el 0 y el 99.999, pusimos como condici\u00f3n que tuviese las cinco cifras distintas y que, adem\u00e1s, cumpliese alguna otra propiedad interesante. Finalmente hemos conseguido un n\u00famero que tiene la siguiente propiedad: si numeramos los meses del a\u00f1o del 1 al 12, en cualquier mes del a\u00f1o ocurre que al restar a nuestro n\u00famero de loter\u00eda el n\u00famero del mes anterior, el resultado es divisible por el n\u00famero del mes en el que estemos. Y esto sucede para cada uno de los meses del a\u00f1o.  <\/p>\n<p>Es decir, si llamamos L a nuestro n\u00famero, tenemos por ejemplo que en marzo L-2 es divisible entre 3 y en diciembre L-11 es divisible entre 12. <\/p>\n<p>El reto que os planteamos es que nos dig\u00e1is a qu\u00e9 n\u00famero de Loter\u00eda estamos abonados.\n<\/p><\/blockquote>\n<p>He elaborado una relaci\u00f3n de ejercicios (para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> y para la siguiente versi\u00f3n del libro <a href=\"http:\/\/www.cs.us.es\/~jalonso\/publicaciones\/Piensa_en_Haskell.pdf\">Piensa en Haskell<\/a>) en la que se generaliza el problema y se resuelve con Haskell de cuatro maneras distintas. La relaci\u00f3n de ejercicios es la siguiente<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List (nub)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 1\u00aa soluci\u00f3n (por fuerza bruta)                                   --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Un n\u00famero n es casi curioso de orden k si tiene la\n-- siguiente propiedad: para cada i entre 1 y k, n-i es divisible por i. \n-- \n-- Definir la funci\u00f3n\n--    esCasiCurioso :: Integer -> Integer -> Bool\n-- tal que (esCasiCurioso k n) se verifica si n es casi curioso de orden\n-- k. Por ejemplo, \n--    esCasiCurioso 3 17  ==  True\n--    esCasiCurioso 4 17  ==  False\n-- ---------------------------------------------------------------------\n\nesCasiCurioso :: Integer -> Integer -> Bool\nesCasiCurioso k n = and [(n-i+1) `mod` i == 0 | i <- [1..k]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    casiCuriosos1 :: Integer -> [Integer]\n-- tal que (casiCuriosos1 k) es la lista de los n\u00fameros casi curiosos de\n-- orden k. Por ejemplo, \n--    take 5 (casiCuriosos1 4)  ==  [11,23,35,47,59]\n-- ---------------------------------------------------------------------\n\ncasiCuriosos1 :: Integer -> [Integer]\ncasiCuriosos1 k = [n | n <- [1..], esCasiCurioso k n]\n                       \n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    conCifras :: Integer -> [Integer] -> [Integer]\n-- tal que (conCifras k xs) es la lista de n\u00fameros con k cifras de la\n-- lista creciente de n\u00fameros xs. Por ejemplo, \n--    conCifras 2 [7,17..]  ==  [17,27,37,47,57,67,77,87,97]\n-- ---------------------------------------------------------------------\n\nconCifras :: Integer -> [Integer] -> [Integer]\nconCifras k xs =\n    takeWhile (<=10^k-1) (dropWhile (<10^(k-1)) xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    cifrasDistintas :: Integer -> Bool\n-- tal que (cifrasDistintas n) se verifica si n es un n\u00famero con sus\n-- cifras distintas. Por ejemplo,\n--    cifrasDistintas 325476  ==  True\n--    cifrasDistintas 325426  ==  False\n-- ---------------------------------------------------------------------\n\ncifrasDistintas :: Integer -> Bool\ncifrasDistintas n = length cifras == length (nub cifras)\n    where cifras = show n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    conCifrasDistintas :: [Integer] -> [Integer]\n-- tal que (conCifrasDistintas xs) es la lista de n\u00fameros de xs que\n-- tienen sus cifras distintas. Por ejemplo,\n--    conCifrasDistintas [27719,55439,83159]  ==  [83159]\n-- ---------------------------------------------------------------------\n\nconCifrasDistintas :: [Integer] -> [Integer]\nconCifrasDistintas = filter cifrasDistintas\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Un n\u00famero n es curioso si es curioso de tipo A y sus\n-- cifras son distintas.\n-- \n-- Definir la funci\u00f3n\n--    curiosos1 :: Integer -> [Integer]\n-- tal que (curiosos1 k m) es la lista de los n\u00fameros curiosos de orden\n-- k con m cifras. Por ejemplo,\n--    curiosos1 9 4  ==  [2519,5039]\n-- ---------------------------------------------------------------------\n\ncuriosos1 :: Integer -> Integer -> [Integer]\ncuriosos1 k m = conCifrasDistintas (conCifras m (casiCuriosos1 k))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Calcular la soluci\u00f3n del desaf\u00edo matem\u00e1tico.\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> head (curiosos1 12 5)\n--    83159\n\n-- ---------------------------------------------------------------------\n-- \u00a7 2\u00aa soluci\u00f3n (con casiCuriosos por recursi\u00f3n)                                      --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir, por recursi\u00f3n, la funci\u00f3n\n--    casiCuriosos2 :: Integer -> [Integer]\n-- tal que (casiCuriosos2 k) es la lista de los n\u00fameros casi curiosos de\n-- orden k. Por ejemplo, \n--    take 5 (casiCuriosos2 4)  ==  [11,23,35,47,59]\n-- ---------------------------------------------------------------------\n\ncasiCuriosos2 :: Integer -> [Integer]\ncasiCuriosos2 1 = [1..]\ncasiCuriosos2 k = [n | n <- casiCuriosos2 (k-1), (n-k+1) `mod` k == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    curiosos2 :: Integer -> [Integer]\n-- tal que (curiosos2 k m) es la lista de los n\u00fameros curiosos de orden\n-- k con m cifras. Por ejemplo,\n--    curiosos2 9 4  ==  [2519,5039]\n-- ---------------------------------------------------------------------\n\ncuriosos2 :: Integer -> Integer -> [Integer]\ncuriosos2 k m = conCifrasDistintas (conCifras m (casiCuriosos2 k))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Comparar los recursos necesarios para evaluar las\n-- siguientes expresiones\n--    head (curiosos1 12 7)\n--    head (curiosos2 12 7)\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    ghci> head (curiosos1 12 7)\n--    1025639\n--    (19.05 secs, 770789772 bytes)\n--    ghci> head (curiosos2 12 7)\n--    1025639\n--    (8.34 secs, 315892320 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Por recursi\u00f3n                                                    --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir, por recursi\u00f3n, la funci\u00f3n\n--    curiosos3 :: Integer -> Integer -> [Integer]\n-- tal que (curiosos3 k m) es la lista de los n\u00fameros curiosos de orden\n-- k con m cifras. Por ejemplo,\n--    curiosos3 9 4  ==  [2519,5039]\n-- ---------------------------------------------------------------------\n\ncuriosos3 :: Integer -> Integer -> [Integer]\ncuriosos3 1 m = conCifrasDistintas [10^(m-1)..10^m-1]\ncuriosos3 k m = [n | n <- curiosos3 (k-1) m, (n-k+1) `mod` k == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Comparar los recursos necesarios para evaluar las\n-- siguientes expresiones\n--    head (curiosos2 12 7)\n--    head (curiosos3 12 7)\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    ghci> head (curiosos2 12 7)\n--    1025639\n--    (8.34 secs, 315892320 bytes)\n--    ghci> head (curiosos3 12 7)\n--    1025639\n--    (0.19 secs, 14468104 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 4\u00aa soluci\u00f3n (por propiedades observadas)                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    diferencias :: [Integer] -> [Integer]\n-- tal que (diferencias xs) es la lista de la diferencia de cada\n-- elemento de xs por su anterior. Por ejemplo,\n--    diferencias [3,5,6,11]  ==  [2,1,5]\n-- ---------------------------------------------------------------------\n\ndiferencias :: [Integer] -> [Integer]\ndiferencias xs = zipWith (-) (tail xs) xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Calcular el valor de las siguientes expresiones\n--    diferencias (take 5 (casiCuriosos1 2))\n--    diferencias (take 5 (casiCuriosos1 3))\n--    diferencias (take 5 (casiCuriosos1 4))\n--    diferencias (take 5 (casiCuriosos1 5))\n--    diferencias (take 5 (casiCuriosos1 5))\n-- \u00bfQu\u00e9 se observa?\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> diferencias (take 5 (casiCuriosos1 2))\n--    [2,2,2,2]\n--    ghci> diferencias (take 5 (casiCuriosos1 3))\n--    [6,6,6,6]\n--    ghci> diferencias (take 5 (casiCuriosos1 4))\n--    [12,12,12,12]\n--    ghci> diferencias (take 5 (casiCuriosos1 5))\n--    [60,60,60,60]\n--    ghci> diferencias (take 5 (casiCuriosos1 6))\n--    [60,60,60,60]\n-- \n-- Se observa que todas las diferencias son iguales (es decir son\n-- progresiones aritm\u00e9ticas). \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    mcm :: [Integer] -> Integer\n-- tal que (mcm xs) es el m\u00ednimo com\u00fan m\u00faltiplo de los n\u00fameros de xs. \n-- Por ejemplo,\n--    mcm [2,6,4,5]  ==  60\n-- ---------------------------------------------------------------------\n\nmcm :: [Integer] -> Integer\nmcm = foldr1 lcm\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Calcular el valor de (mcm [1..k]) para k entre 1 y 6. \n-- \u00bfQu\u00e9 relaci\u00f3n se observa a partir de los c\u00e1lculos del ejercicio 14?\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> [(k,mcm [1..k]) | k <- [1..6]]\n--    [(1,1),(2,2),(3,6),(4,12),(5,60),(6,60)]\n-- \n-- Se observa que, para cada k, (casiCuriosos1 5) es una progresi\u00f3n\n-- aritm\u00e9tica cuya diferencia es el m\u00ednimo com\u00fan m\u00faltiplo de 1,2,..k. \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Calcular el valor de las siguientes expresiones\n--    head (casiCuriosos1 2)\n--    head (casiCuriosos1 3)\n--    head (casiCuriosos1 4)\n--    head (casiCuriosos1 5)\n--    head (casiCuriosos1 6)\n-- \u00bfQu\u00e9 relaci\u00f3n se observa entre (head (casiCuriosos1 k)) y k?\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> head (casiCuriosos1 2)\n--    1\n--    ghci> head (casiCuriosos1 3)\n--    5\n--    ghci> head (casiCuriosos1 4)\n--    11\n--    ghci> head (casiCuriosos1 5)\n--    59\n--    ghci> head (casiCuriosos1 6)\n--    59\n--    \n-- Se observa que el primer elemento de (casiCuriosos1 k) es el m\u00ednimo\n-- com\u00fan m\u00faltiplo de 1,2,..k menos 1. \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Usando las observaciones de los ejercicios anteriores,\n-- definir la funci\u00f3n\n--    casiCuriosos4 :: Integer -> [Integer]\n-- tal que (casiCuriosos4 k) es la lista de los n\u00fameros casi curiosos de\n-- orden k. Por ejemplo, \n--    take 5 (casiCuriosos4 4)  ==  [11,23,35,47,59]\n-- ---------------------------------------------------------------------\n\ncasiCuriosos4 :: Integer -> [Integer]\ncasiCuriosos4 k = [a-1,2*a-1..]\n    where a = mcm [1..k]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    curiosos4 :: Integer -> Integer -> [Integer]\n-- tal que (curiosos4 k m) es la lista de los n\u00fameros curiosos de orden\n-- k con m cifras. Por ejemplo,\n--    curiosos4 9 4  ==  [2519,5039]\n-- ---------------------------------------------------------------------\n\ncuriosos4 :: Integer -> Integer -> [Integer]\ncuriosos4 k m = conCifrasDistintas (conCifras m (casiCuriosos4 k))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Comparar los recursos necesarios para evaluar las\n-- siguientes expresiones\n--    head (curiosos3 12 7)\n--    head (curiosos4 12 7)\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    ghci> head (curiosos3 12 7)\n--    1025639\n--    (0.16 secs, 14297500 bytes)\n--    ghci> head (curiosos4 12 7)\n--    1025639\n--    (0.01 secs, 0 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Comparar los recursos necesarios para resolver el\n-- desaf\u00edo con las cuatro definiciones.\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> head (curiosos1 12 5)\n--    83159\n--    (1.48 secs, 62312260 bytes)\n--    ghci> head (curiosos2 12 5)\n--    83159\n--    (0.69 secs, 25715892 bytes)\n--    ghci> head (curiosos3 12 5)\n--    83159\n--    (0.62 secs, 41017896 bytes)\n--    ghci> head (curiosos4 12 5)\n--    83159\n--    (0.01 secs, 750248 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Nota final                                                       --\n-- ---------------------------------------------------------------------\n\n-- Se podr\u00eda haber planteado desde el principio la cuarta soluci\u00f3n\n-- observando que los n\u00fameros casi curiosos de orden k son las\n-- soluciones del sistema de ecuaciones\n--    x = 1 (mod 2)\n--    x = 2 (mod 3)\n--    ...\n--    x = k-1 (mod k)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En El Pa\u00eds del d\u00eda 16 se present\u00f3 el desaf\u00edo matem\u00e1tico Un n\u00famero curios cuyo enunciado es el siguiente: El equipo que preparamos los desaf\u00edos matem\u00e1ticos hemos decidido abonarnos durante todo el a\u00f1o a un n\u00famero de la Loter\u00eda. Para elegir ese n\u00famero, que debe estar comprendido entre el 0 y el 99.999, pusimos como&#8230;<\/p>\n","protected":false},"author":2,"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":[5,221],"tags":[254,270,299],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3965"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=3965"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3965\/revisions"}],"predecessor-version":[{"id":5272,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3965\/revisions\/5272"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3965"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3965"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}