{"id":3123,"date":"2017-03-23T06:00:48","date_gmt":"2017-03-23T04:00:48","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3123"},"modified":"2017-03-31T05:56:41","modified_gmt":"2017-03-31T03:56:41","slug":"numero-de-digitos-del-factorial","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-digitos-del-factorial\/","title":{"rendered":"N\u00famero de d\u00edgitos del factorial"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   nDigitosFact :: Integer -> Integer\n   graficas     :: [Integer] -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(nDigitosFact n) es el n\u00famero de d\u00edgitos de n!. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nDigitosFact 0        ==  1\n     nDigitosFact 4        ==  2\n     nDigitosFact 5        ==  3\n     nDigitosFact 10       ==  7\n     nDigitosFact 100      ==  158\n     nDigitosFact 1000     ==  2568\n     nDigitosFact 10000    ==  35660\n     nDigitosFact 100000   ==  456574\n     nDigitosFact 1000000  ==  5565709\n<\/pre>\n<ul>\n<li>(graficas xs) dibuja las gr\u00e1ficas de los n\u00fameros de d\u00edgitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png?resize=640%2C480\" alt=\"Numero_de_digitos_del_factorial\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3124\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2017\/03\/Numero_de_digitos_del_factorial.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<p><strong>Nota<\/strong>: Este ejercicio est\u00e1 basado en el problema <a href=\"http:\/\/bit.ly\/2o0pkq2\">How many digits?<\/a> de <a href=\"https:\/\/open.kattis.com\">Kattis<\/a> en donde se impone la restricci\u00f3n de calcular, <strong>en menos de 1 segundo<\/strong>, el n\u00famero de d\u00edgitos de los factoriales de 10.000 n\u00fameros del rango [0,1.000.000].<\/p>\n<p>Se puede simular como sigue<\/p>\n<pre lang=\"text\">\n   \u03bb> import System.Random \n   \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]\n   \u03bb> maximum (map nDigitosFact xs)\n   5561492\n   \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]\n   \u03bb> maximum (map nDigitosFact xs)\n   5563303\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, genericIndex)\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa definici\u00f3n\nnDigitosFact1 :: Integer -> Integer\nnDigitosFact1 n =\n  genericLength (show (product [1..n]))\n\n-- 2\u00aa definici\u00f3n (usando logaritmos)\n-- =================================\n\n-- Basado en\n--    nDigitos (n!) = 1 + floor (log (n!))\n--                  = 1 + floor (log (1*2*3*...*n))\n--                  = 1 + floor (log(1) + log(2) + log(3) +...+ log(n))\n\nnDigitosFact2 :: Integer -> Integer\nnDigitosFact2 n =\n  1 + floor (sum [logBase 10 (fromIntegral k) | k <- [1..n]])\n\n-- 3\u00aa definici\u00f3n (usando logaritmos y programaci\u00f3n din\u00e1mica)\n-- =========================================================\n\nnDigitosFact3 :: Integer -> Integer\nnDigitosFact3 0 = 1\nnDigitosFact3 n = 1 + floor ((sumLogs `genericIndex` (n-1)) \/ log 10)\n\nlogs :: [Double]\nlogs = map log [1..]\n\nsumLogs :: [Double]\nsumLogs = scanl1 (+) logs\n\n-- 4\u00aa definici\u00f3n (Usando la f\u00f3rmula de Kamenetsky)\n-- ===============================================\n\n-- La f\u00f3rmula se encuentra en https:\/\/oeis.org\/A034886\n\nnDigitosFact4 :: Integer -> Integer\nnDigitosFact4 0 = 1\nnDigitosFact4 1 = 1\nnDigitosFact4 n =\n  1 + floor (m * logBase 10 (m\/e) + logBase 10 (2*pi*m)\/2)\n  where m = fromIntegral n\n        e = exp 1\n\n--    \u03bb> nDigitosFact1 (4*10^4)\n--    166714\n--    (5.61 secs, 1,649,912,864 bytes)\n--    \u03bb> nDigitosFact2 (4*10^4)\n--    166714\n--    (0.10 secs, 13,741,360 bytes)\n--\n--    \u03bb> nDigitosFact2 (7*10^5)\n--    3787566\n--    (1.86 secs, 187,666,328 bytes)\n--    \u03bb> nDigitosFact3 (7*10^5)\n--    3787566\n--    (0.02 secs, 0 bytes)\n--    \u03bb> nDigitosFact3 (7*10^5)\n--    3787566\n--    (1.01 secs, 238,682,064 bytes)\n--    \u03bb> nDigitosFact4 (7*10^5)\n--    3787566\n--    (0.01 secs, 0 bytes)\n-- \n--    \u03bb> import System.Random \n--    \u03bb> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^2]]\n--    \u03bb> maximum (map nDigitosFact3 xs)\n--    5565097\n--    (11.19 secs, 7,336,595,440 bytes)\n--    \u03bb> maximum (map nDigitosFact4 xs)\n--    5565097\n--    (0.01 secs, 0 bytes)\n\ngraficas :: [Integer] -> IO ()\ngraficas xs = \n    plotLists [Key Nothing]\n              [p1, p2]\n    where p1, p2 :: [(Float, Float)]\n          p1 = [(fi k, fi (nDigitosFact4 k)) | k <- xs]\n          p2 = [(k',5.5*k') | k <- xs, let k' = fi k]\n          fi = fromIntegral  \n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones nDigitosFact :: Integer -> Integer graficas :: [Integer] -> IO () tales que (nDigitosFact n) es el n\u00famero de d\u00edgitos de n!. Por ejemplo, nDigitosFact 0 == 1 nDigitosFact 4 == 2 nDigitosFact 5 == 3 nDigitosFact 10 == 7 nDigitosFact 100 == 158 nDigitosFact 1000 == 2568 nDigitosFact 10000 == 35660&#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":[8,386,282,183,256,258,385,314,10,11,366,157,252,33,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3123"}],"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=3123"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3123\/revisions"}],"predecessor-version":[{"id":3165,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3123\/revisions\/3165"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}