{"id":1356,"date":"2011-05-09T14:06:35","date_gmt":"2011-05-09T14:06:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1356"},"modified":"2011-05-09T14:08:49","modified_gmt":"2011-05-09T14:08:49","slug":"sorpresa-sumando-potencias-de-2-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/sorpresa-sumando-potencias-de-2-en-haskell\/","title":{"rendered":"&#8220;Sorpresa sumando potencias de 2&#8221; en Haskell"},"content":{"rendered":"<p>Recientemente, se public\u00f3 en Gaussianos el art\u00edculo <a href=\"http:\/\/gaussianos.com\/sorpresa-sumando-potencias-de-2\/\">Sorpresa sumando potencias de 2<\/a> en el que se comentaba c\u00f3mo, a partir de las representaciones de los n\u00fameros naturales como sumas de potencias de 2 se puede obtener una enumeraci\u00f3n de los racionales. Tambi\u00e9n se comentaba la equivalencia de la numeraci\u00f3n anterior con el recorrido en anchura del \u00e1rbol de Calkin-Wilf.<\/p>\n<p>A partir de dicho art\u00edculo y sus fuentes (el art\u00edculo de Neil Calkin y Herbert S. Wilf <a href=\"http:\/\/www.math.clemson.edu\/~calkin\/Papers\/calkin_wilf_recounting_rationals.pdf\">Recounting the rationals<\/a> y el art\u00edculo de la wikipedia <a href=\"http:\/\/en.wikipedia.org\/wiki\/Calkin%E2%80%93Wilf_tree\">Calkin-Wilf tree<\/a>), he elaborado la siguiente relaci\u00f3n de ejercicios de Haskell para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>. <\/p>\n<p>En la relaci\u00f3n se incluye tanto la construcci\u00f3n de las dos enumeraciones en Haskell como la verificaci\u00f3n de sus propiedades con QuickCheck. Finalmente, se incluye el c\u00e1lculo del n\u00famero de las representaciones hiperbinarias mediante la funci\u00f3n &#8220;fucs&#8221;.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Numeraci\u00f3n de los racionales mediante representaciones hiperbinarias\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la constante\r\n--    potenciasDeDos :: [Integer]\r\n-- tal que potenciasDeDos es la lista de las potencias de 2. Por\r\n-- ejemplo, \r\n--    take 10 potenciasDeDos  ==  [1,2,4,8,16,32,64,128,256,512]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciasDeDos :: [Integer]\r\npotenciasDeDos = [2^n | n <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    empiezaConDos x (y1:y2:ys) = y1 == x &#038;&#038; y2 == x\r\n-- tal que (empiezaConDos x ys) se verifica si los dos primeros\r\n-- elementos de ys son iguales a x. Por ejemplo,\r\n--    empiezaConDos 5 [5,5,3,7]  ==  True\r\n--    empiezaConDos 5 [5,3,5,7]  ==  False\r\n--    empiezaConDos 5 [5,5,5,7]  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nempiezaConDos x (y1:y2:ys) = y1 == x &#038;&#038; y2 == x\r\nempiezaConDos x _          = False\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    representacionesHB :: Integer -> [[Integer]]\r\n-- tal que (representacionesHB n) es la lista de las representaciones\r\n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\r\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo\r\n--    representacionesHB 5  ==  [[1,2,2],[1,4]]\r\n--    representacionesHB 6  ==  [[1,1,2,2],[1,1,4],[2,4]]\r\n-- ---------------------------------------------------------------------\r\n\r\nrepresentacionesHB :: Integer -> [[Integer]]\r\nrepresentacionesHB n = representacionesHB' n potenciasDeDos\r\nrepresentacionesHB' n (x:xs)\r\n    | n == 0    = [[]]\r\n    | x == n    = [[x]]\r\n    | x <  n    = [x:ys | ys <- representacionesHB' (n-x) (x:xs),\r\n                          not (empiezaConDos x ys)] ++\r\n                  representacionesHB' n xs\r\n    | otherwise = []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    nRepresentacionesHB :: Integer -> Integer\r\n-- tal que (nRepresentacionesHB n) es el n\u00famero de las representaciones \r\n-- hiperbinarias del n\u00famero n como suma de potencias de 2 donde cada\r\n-- sumando aparece como m\u00e1ximo 2 veces. Por ejemplo,\r\n--    ghci> [nRepresentacionesHB n | n <- [0..20]]\r\n--    [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8]\r\n-- ---------------------------------------------------------------------\r\n\r\nnRepresentacionesHB :: Integer -> Integer\r\nnRepresentacionesHB = genericLength . representacionesHB\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    termino :: Integer -> (Integer,Integer)\r\n-- tal que (termino n) es el par formado por el n\u00famero de\r\n-- representaciones hiperbinarias de n y de n+1 (que se interpreta como \r\n-- su cociente). Por ejemplo, \r\n--    termino 4  ==  (3,2)\r\n-- ---------------------------------------------------------------------\r\n\r\ntermino :: Integer -> (Integer,Integer)\r\ntermino n = (nRepresentacionesHB n, nRepresentacionesHB (n+1))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    sucesionHB :: [(Integer,Integer)]\r\n-- sucesionHB es la la sucesi\u00f3n cuyo t\u00e9mino n-\u00e9simo es (termino n); es\r\n-- decir, el par formado por el n\u00famero de representaciones hiperbinarias\r\n-- de n y de n+1. Por ejemplo, \r\n--    ghci> take 10 sucesionHB\r\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionHB :: [(Integer,Integer)]\r\nsucesionHB = [termino n | n <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Comprobar con QuickCheck que, para todo n,\r\n-- (nRepresentacionesHB n) y  (nRepresentacionesHB (n+1)) son primos\r\n-- entre s\u00ed. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_irreducibles :: Integer -> Property\r\nprop_irreducibles n =\r\n    n >= 0 ==> \r\n    gcd (nRepresentacionesHB n) (nRepresentacionesHB (n+1)) == 1\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_irreducibles\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Comprobar con QuickCheck que todos los elementos de la\r\n-- sucesionHB son distintos.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_distintos :: Integer -> Integer -> Bool\r\nprop_distintos n m =\r\n    termino n' \/= termino m'\r\n    where n' = abs n\r\n          m' = n' + abs m + 1\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_distintos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n\r\n--    contenido :: Integer -> Integer -> Bool\r\n-- tal que (contenido n) se verifica si la expresiones reducidas de\r\n-- todas las fracciones x\/y, con x e y entre 1 y n, pertenecen a la\r\n-- sucesionHB. Por ejemplo,  \r\n--    contenidos 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\ncontenido :: Integer -> Bool\r\ncontenido n =\r\n    and [pertenece (reducida (x,y)) sucesionHB |\r\n         x <- [1..n], y <- [1..n]]\r\n    where pertenece x (y:ys) = x == y || pertenece x ys\r\n          reducida (x,y) = (x `div` z, y `div` z)\r\n              where z = gcd x y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    indice :: (Integer,Integer) -> Integer\r\n-- tal que (indice (a,b)) es el \u00edndice del par (a,b) en la sucesi\u00f3n de\r\n-- los racionales. Por ejemplo, \r\n--    indice (3,2)  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nindice :: (Integer,Integer) -> Integer\r\nindice (a,b) = head [n | (n,(x,y)) <- zip [0..] sucesionHB, \r\n                         (x,y) == (a,b)] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Numeraciones mediante \u00e1rboles de Calkin-Wilf                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El \u00e1rbol de Calkin-Wilf es el \u00e1rbol definido por las siguientes\r\n-- reglas:\r\n--    * El nodo ra\u00edz es el (1,1)\r\n--    * Los hijos del nodo (x,y) son (x,x+y) y (x+y,y)\r\n-- Por ejemplo, los 4 primeros niveles del \u00e1rbol de Calkin-Wilf son \r\n--                         (1,1)\r\n--                           |\r\n--               +-----------+-----------+\r\n--               |                       |\r\n--             (1,2)                   (2,1)\r\n--               |                       |\r\n--         +-----+-----+           +-----+-----+\r\n--         |           |           |           |\r\n--       (1,3)       (3,2)       (2,3)       (3,1)\r\n--         |           |           |           |         \r\n--      +--+--+     +--+--+     +--+--+     +--+--+\r\n--      |     |     |     |     |     |     |     | \r\n--    (1,4) (4,3) (3,5) (5,2) (2,5) (5,3) (3,4) (4,1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n \r\n--    sucesores :: (Integer,Integer) -> [(Integer,Integer)]\r\n-- tal que (sucesores (x,y)) es la lista de los hijos del par (x,y) en\r\n-- el \u00e1rbol de Calkin-Wilf. Por ejemplo, \r\n--    sucesores (3,2)  ==  [(3,5),(5,2)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesores :: (Integer,Integer) -> [(Integer,Integer)]\r\nsucesores (x,y) = [(x,x+y),(x+y,y)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    siguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\r\n-- tal que (siguiente xs) es la lista formada por los hijos de los\r\n-- elementos de xs en el \u00e1rbol de Calkin-Wilf. Por ejemplo, \r\n--    ghci> siguiente [(1,3),(3,2),(2,3),(3,1)]\r\n--    [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguiente :: [(Integer,Integer)] -> [(Integer,Integer)]\r\nsiguiente xs = [p | x <- xs, p <- sucesores x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la constante\r\n--    nivelesCalkinWilf:: [[(Integer,Integer)]]\r\n-- tal que nivelesCalkinWilf es la lista de los niveles del \u00e1rbol de\r\n-- Calkin-Wilf. Por ejemplo, \r\n--    ghci> take 4 nivelesCalkinWilf\r\n--    [[(1,1)],\r\n--     [(1,2),(2,1)],\r\n--     [(1,3),(3,2),(2,3),(3,1)],\r\n--     [(1,4),(4,3),(3,5),(5,2),(2,5),(5,3),(3,4),(4,1)]]\r\nnivelesCalkinWilf:: [[(Integer,Integer)]]\r\nnivelesCalkinWilf = iterate siguiente [(1,1)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la constante \r\n--    sucesionCalkinWilf :: [(Integer,Integer)]\r\n-- tal que sucesionCalkinWilf es la lista correspondiente al recorrido\r\n-- en anchura del \u00e1rbol de Calkin-Wilf. Por ejemplo,\r\n--    ghci> take 10 sucesionCalkinWilf\r\n--    [(1,1),(1,2),(2,1),(1,3),(3,2),(2,3),(3,1),(1,4),(4,3),(3,5)]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionCalkinWilf :: [(Integer,Integer)]\r\nsucesionCalkinWilf = concat nivelesCalkinWilf\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir la funci\u00f3n\r\n--    igual_sucesion_HB_CalkinWilf :: Int -> Bool\r\n-- tal que (igual_sucesion_HB_CalkinWilf n) se verifica si los n\r\n-- primeros t\u00e9rminos de la sucesi\u00f3n HB son iguales que los de la\r\n-- sucesi\u00f3n de Calkin-Wilf. Por ejemplo,\r\n--    igual_sucesion_HB_CalkinWilf 20  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nigual_sucesion_HB_CalkinWilf :: Int -> Bool\r\nigual_sucesion_HB_CalkinWilf n =\r\n    take n sucesionCalkinWilf == take n sucesionHB\r\n\r\n-- ---------------------------------------------------------------------\r\n-- N\u00famero de representaciones hiperbinarias mediante la funci\u00f3n fusc\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    fusc :: Integer -> Integer\r\n-- tal que \r\n--    fusc(0)    = 1\r\n--    fusc(2n+1) = fusc(n)\r\n--    fusc(2n+2) = fusc(n+1)+fusc(n)\r\n-- Por ejemplo,\r\n--    fusc 4  ==  3\r\n-- ---------------------------------------------------------------------\r\n\r\nfusc :: Integer -> Integer\r\nfusc 0 = 1\r\nfusc  n | odd n     = fusc ((n-1) `div` 2)\r\n        | otherwise = fusc(m+1) + fusc m\r\n                      where m = (n-2) `div` 2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Comprobar con QuickCheck que, para todo n, (fusc n) es\r\n-- el n\u00famero de las representaciones hiperbinarias del n\u00famero n como\r\n-- suma de potencias de 2 donde cada sumando aparece como m\u00e1ximo 2\r\n-- veces; es decir, que las funciones fusc y nRepresentacionesHB son\r\n-- equivalentes. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_fusc :: Integer -> Bool\r\nprop_fusc n = nRepresentacionesHB n' == fusc n'\r\n              where n' = abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_fusc\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Recientemente, se public\u00f3 en Gaussianos el art\u00edculo Sorpresa sumando potencias de 2 en el que se comentaba c\u00f3mo, a partir de las representaciones de los n\u00fameros naturales como sumas de potencias de 2 se puede obtener una enumeraci\u00f3n de los racionales. Tambi\u00e9n se comentaba la equivalencia de la numeraci\u00f3n anterior con el recorrido en anchura&#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],"tags":[174],"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\/1356"}],"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=1356"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1356\/revisions"}],"predecessor-version":[{"id":1358,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1356\/revisions\/1358"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1356"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1356"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1356"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}