{"id":7049,"date":"2022-05-25T13:28:17","date_gmt":"2022-05-25T11:28:17","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7049"},"modified":"2022-05-25T13:28:56","modified_gmt":"2022-05-25T11:28:56","slug":"numeracion-con-base-multiple","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeracion-con-base-multiple\/","title":{"rendered":"Numeraci\u00f3n con base m\u00faltiple"},"content":{"rendered":"<p>Sea (b(i) | i \u2265 1) una sucesi\u00f3n infinita de n\u00fameros enteros mayores que 1. Entonces todo entero x mayor que cero se puede escribir de forma \u00fanica como<\/p>\n<pre lang=\"text\">\n   x = x(0) + x(1)b(1) +x(2)b(1)b(2) + ... + x(n)b(1)b(2)...b(n)\n<\/pre>\n<p>donde cada x(i) satisface la condici\u00f3n 0 \u2264 x(i) &lt; b(i+1). Se dice que [x(n),x(n-1),&#8230;,x(2),x(1),x(0)] es la representaci\u00f3n de x en la base (b(i)). Por ejemplo, la representaci\u00f3n de 377 en la base (2, 6, 8, &#8230;) es [7,5,0,1] ya que<\/p>\n<pre lang=\"text\">\n   377 = 1 + 0*2 + 5*2*4 + 7*2*4*6\n<\/pre>\n<p>y, adem\u00e1s, 0 \u2264 1 &lt; 2, 0 \u2264 0 &lt; 4, 0 \u2264 5 &lt; 6 y 0 \u2264 7 &lt; 8.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   decimalAmultiple :: [Integer] -> Integer -> [Integer]\n   multipleAdecimal :: [Integer] -> [Integer] -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(decimalAmultiple bs x) es la representaci\u00f3n del n\u00famero x en la base bs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]\n     decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]\n     decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]\n     decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]\n<\/pre>\n<ul>\n<li>(multipleAdecimal bs cs) es el n\u00famero decimal cuya  representaci\u00f3n en la base bs es cs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     multipleAdecimal [2,4..] [7,5,0,1]                ==  377\n     multipleAdecimal [2,5..] [4,5,3,1]                ==  377\n     multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015\n     multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015\n<\/pre>\n<p>Comprobar con QuickCheck que se verifican las siguientes propiedades<\/p>\n<ul>\n<li>Para cualquier base bs y cualquier entero positivo n,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     multipleAdecimal bs (decimalAmultiple bs x) == x\n<\/pre>\n<ul>\n<li>Para cualquier base bs y cualquier entero positivo n, el coefiente i-\u00e9simo de la representaci\u00f3n m\u00faltiple de n en la base bs es un entero no negativo menos que el i-\u00e9simo elemento de bs.<\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\nimport Data.List (unfoldr)\n\n-- 1\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple1 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple1 bs n = reverse (aux bs n)\n  where aux _ 0      = []\n        aux (d:ds) m = r : aux ds q\n          where (q,r) = quotRem m d\n\n-- 2\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple2 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple2 bs n = aux bs n []\n  where aux _ 0  xs     = xs\n        aux (d:ds) m xs = aux ds q (r:xs)\n          where (q,r) = quotRem m d\n\n-- 3\u00aa soluci\u00f3n de decimalAmultiple\n-- ===============================\n\ndecimalAmultiple3 :: [Integer] -> Integer -> [Integer]\ndecimalAmultiple3 xs n = reverse (unfoldr f (xs,n))\n  where f (_     ,0) = Nothing\n        f ((y:ys),m) = Just (r,(ys,q))\n                       where (q,r) = quotRem m y\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_decimalAmultiple :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_decimalAmultiple (InfiniteList xs _) (Positive n) =\n  all (== decimalAmultiple1 xs' n)\n      [decimalAmultiple2 xs' n,\n       decimalAmultiple3 xs' n]\n  where xs' = map getPositive xs\n\n-- Comparaci\u00f3n de eficiencia de decimalAmultiple\n-- =============================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (decimalAmultiple1 [2,7..] (10^(10^5)))\n--    21731\n--    (0.45 secs, 486,085,256 bytes)\n--    \u03bb> length (decimalAmultiple2 [2,7..] (10^(10^5)))\n--    21731\n--    (0.32 secs, 485,563,664 bytes)\n--    \u03bb> length (decimalAmultiple3 [2,7..] (10^(10^5)))\n--    21731\n--    (0.44 secs, 487,649,768 bytes)\n\n-- 1\u00aa soluci\u00f3n de multipleAdecimal\n-- ===============================\n\nmultipleAdecimal1  :: [Integer] -> [Integer] -> Integer\nmultipleAdecimal1 xs ns = aux xs (reverse ns)\n  where aux (y:ys) (m:ms) = m + y * (aux ys ms)\n        aux _ _           = 0\n\n-- 2\u00aa soluci\u00f3n de multipleAdecimal\n-- ===============================\n\nmultipleAdecimal2 :: [Integer] -> [Integer] -> Integer\nmultipleAdecimal2 bs xs =\n  sum (zipWith (*) (reverse xs) (1 : scanl1 (*) bs))\n\n-- Comprobaci\u00f3n de equivalencia de multipleAdecimal\n-- ================================================\n\n-- La propiedad es\nprop_multipleAdecimal :: InfiniteList (Positive Integer) -> [Positive Integer] -> Bool\nprop_multipleAdecimal (InfiniteList xs _) ys =\n  multipleAdecimal1 xs' ys' == multipleAdecimal2 xs' ys'\n  where xs' = map getPositive xs\n        ys' = map getPositive ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_multipleAdecimal\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de multipleAdecimal\n-- =============================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (multipleAdecimal1 [2,3..] [1..10^4]))\n--    35660\n--    (0.14 secs, 179,522,152 bytes)\n--    \u03bb> length (show (multipleAdecimal2 [2,3..] [1..10^4]))\n--    35660\n--    (0.22 secs, 243,368,664 bytes)\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- La primera propiedad es\nprop_inversas :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_inversas (InfiniteList xs _) (Positive n) =\n  multipleAdecimal1 xs' (decimalAmultiple1 xs' n) == n\n  where xs' = map getPositive xs\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_inversas\n--    +++ OK, passed 100 tests.\n\n-- la 2\u00aa propiedad es\nprop_coeficientes :: InfiniteList (Positive Integer) -> Positive Integer -> Bool\nprop_coeficientes (InfiniteList xs _) (Positive n) =\n  and [0 <= c &#038;&#038; c < b | (c,b) <- zip cs xs']\n  where xs' = map getPositive xs\n        cs = reverse (decimalAmultiple1 xs' n)\n\n-- Su comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_coeficientes\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Numeracion_con_multiples_base.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sea (b(i) | i \u2265 1) una sucesi\u00f3n infinita de n\u00fameros enteros mayores que 1. Entonces todo entero x mayor que cero se puede escribir de forma \u00fanica como x = x(0) + x(1)b(1) +x(2)b(1)b(2) + &#8230; + x(n)b(1)b(2)&#8230;b(n) donde cada x(i) satisface la condici\u00f3n 0 \u2264 x(i) &lt; b(i+1). Se dice que [x(n),x(n-1),&#8230;,x(2),x(1),x(0)] 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":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7049"}],"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=7049"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7049\/revisions"}],"predecessor-version":[{"id":7051,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7049\/revisions\/7051"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}