{"id":2621,"date":"2016-11-28T08:19:46","date_gmt":"2016-11-28T06:19:46","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2621"},"modified":"2016-12-05T08:39:44","modified_gmt":"2016-12-05T06:39:44","slug":"representacion-binaria-de-los-numeros-de-carol","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/representacion-binaria-de-los-numeros-de-carol\/","title":{"rendered":"Representaci\u00f3n binaria de los n\u00fameros de Carol"},"content":{"rendered":"<p>Un <a href=\"http:\/\/bit.ly\/2g982GH\">n\u00famero de Carol<\/a> es un n\u00famero entero de la forma <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=4%5En-2%5E%7Bn%2B1%7D-1&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"4^n-2^{n+1}-1\" class=\"latex\" \/> o, equivalentemente, <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=%282%5En-1%29%5E2-2&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"(2^n-1)^2-2\" class=\"latex\" \/>. Los primeros n\u00fameros de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   carol        :: Integer -> Integer\n   carolBinario :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(carol n) es el n-\u00e9simo n\u00famero de Carol. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     carol  3  ==  47\n     carol  4  ==  223\n     carol 25  ==  1125899839733759\n<\/pre>\n<ul>\n<li>(carolBinario n) es la representaci\u00f3n binaria del n-\u00e9simo n\u00famero de Carol. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     carolBinario 3  ==  101111\n     carolBinario 4  ==  11011111\n     carolBinario 5  ==  1110111111\n<\/pre>\n<p>Comprobar con QuickCheck que, para n > 2, la representaci\u00f3n binaria del n-\u00e9simo n\u00famero de Carol es el n\u00famero formado por n-2 veces el d\u00edgito 1, seguido por un 0 y a continuaci\u00f3n n+1 veces el d\u00edgito 1.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\ncarol :: Integer -> Integer\ncarol n = x^2 - 2\n  where x = 2^n - 1\n\ncarolBinario :: Integer -> Integer\ncarolBinario = binario . carol\n\n-- (binario x) es el n\u00famero binario correspondiente al n\u00famero decimal\n-- x. Por ejemplo, \n--    binario 223  ==  11011111\nbinario :: Integer -> Integer \nbinario = digitosAnumero . reverse . int2bin\n\n-- (int2bin x) es el n\u00famero binario (representado como la lista\n-- invertida de sus d\u00edgitos) correspondiente al n\u00famero decimal\n-- x. Por ejemplo, \n--    int2bin 223  ==  [1,1,1,1,1,0,1,1]\nint2bin :: Integer -> [Integer]\nint2bin n | n < 2     = [n]\n          | otherwise = n `mod` 2 : int2bin (n `div` 2)\n\n-- (digitosAnumero xs) es el n\u00famero cuya lista de d\u00edgitos es xs. Por\n-- ejemplo,  \n--    digitosAnumero [3,2,5]  ==  325\ndigitosAnumero :: [Integer] -> Integer\ndigitosAnumero xs =\n  read (concatMap show xs)\n\n-- En la definici\u00f3n anterior se pueden eliminar el argumento\ndigitosAnumero2 :: [Integer] -> Integer\ndigitosAnumero2 = read . (concatMap show)\n\n-- La propiedad es\nprop_carol :: Integer -> Property\nprop_carol n =\n  n > 2 ==> carolBinario n == carolBinario2 n\n  where\n    carolBinario2 n =\n      digitosAnumero ((replicate (m-2) 1) ++ [0] ++ (replicate (m+1) 1))\n      where m = fromIntegral n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_carol\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Referencias<\/h4>\n<ul>\n<li><a href=\"http:\/\/www.geeksforgeeks.org\/carol-number\">Carol number<\/a> por Shashank Mishra en <a href=\"http:\/\/www.geeksforgeeks.org\">GeeksforGeeks<\/a>.  <\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Carol_number\">Carol number<\/a> en la Wikipedia.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Un n\u00famero de Carol es un n\u00famero entero de la forma o, equivalentemente, . Los primeros n\u00fameros de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527. Definir las funciones carol :: Integer -> Integer carolBinario :: Integer -> Integer tales que (carol n) es el n-\u00e9simo n\u00famero de Carol. Por ejemplo,&#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":[4],"tags":[58,30,183,89,11,95,19,32,33,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2621"}],"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=2621"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2621\/revisions"}],"predecessor-version":[{"id":2654,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2621\/revisions\/2654"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2621"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2621"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2621"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}