{"id":2420,"date":"2012-12-18T17:48:50","date_gmt":"2012-12-18T17:48:50","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2420"},"modified":"2013-03-08T05:47:36","modified_gmt":"2013-03-08T05:47:36","slug":"i1m2012-ceros-finales-del-factorial","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ceros-finales-del-factorial\/","title":{"rendered":"I1M2012: Ceros finales del factorial"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado la soluci\u00f3n con Haskell de un problema propuesto para la Olimpiada Internacional de Matem\u00e1ticas de 1987 cuyo enunciado es<\/p>\n<blockquote><p>\n&#8221;Calcular el menor n\u00famero natural n tal que n! termina exactamente en 1987 ceros.&#8221;\n<\/p><\/blockquote>\n<p>Resolverlo con Haskell.<\/p>\n<p>Para resolverlo, empezamos definiendo la funci\u00f3n cerosDelFactorial tal que (cerosDelFactorial n) es el n\u00famero de ceros en que termina el factorial de n. Por ejemplo, <\/p>\n<pre lang=\"text\"> \r\ncerosDelFactorial1 24  ==  4\r\ncerosDelFactorial1 25  ==  6\r\n<\/pre>\n<p>Presentamos dos definiciones la primera es<\/p>\n<pre lang=\"haskell\">\r\ncerosDelFactorial1 :: Integer -> Integer\r\ncerosDelFactorial1 n = ceros (factorial n)\r\n<\/pre>\n<p>donde (ceros n) es el n\u00famero de ceros en los que termina el n\u00famero n. Por ejemplo, <\/p>\n<pre lang=\"text\">    \r\nceros 320000  ==  4\r\n<\/pre>\n<pre lang=\"haskell\">\r\nceros n | rem n 10 \/= 0 = 0\r\n        | otherwise     = 1 + ceros (div n 10)\r\n<\/pre>\n<p>y (factorial n) es el factorial n. Por ejemplo,<\/p>\n<pre lang=\"text\"> \r\nfactorial 3  ==  6\r\n<\/pre>\n<pre lang=\"haskell\">\r\nfactorial n = product [1..n]\r\n<\/pre>\n<p>La segunda es<\/p>\n<pre lang=\"haskell\">\r\ncerosDelFactorial2 :: Integer -> Integer\r\ncerosDelFactorial2 n | n < 5     = 0\r\n                     | otherwise = m + cerosDelFactorial2 m\r\n                     where m = n `div` 5\r\n<\/pre>\n<p>Se puede comprobar la equivalencia de las dos definiciones<\/p>\n<pre lang=\"text\">\r\nghci> and [cerosDelFactorial1 n == cerosDelFactorial2 n | n <- [1..100]]\r\nTrue\r\n<\/pre>\n<p>y que la segunda es m\u00e1s eficiente<\/p>\n<pre lang=\"text\">\r\nghci> cerosDelFactorial1 (10^4)\r\n2499\r\n(0.64 secs, 131287116 bytes)\r\nghci> cerosDelFactorial2 (10^4)\r\n2499\r\n(0.01 secs, 725088 bytes)\r\n<\/pre>\n<p>En lo que sigue, usaremos la segunda definici\u00f3n <\/p>\n<pre lang=\"haskell\">\r\ncerosDelFactorial :: Integer -> Integer\r\ncerosDelFactorial = cerosDelFactorial1\r\n<\/pre>\n<p>A continuaci\u00f3n definimos la funci\u00f3n menorFactorial tal que (menorFactorial m) es el menor n\u00famero cuyo factorial termina en m ceros exactamente. Por ejemplo,<\/p>\n<pre lang=\"text\"> \r\nmenorFactorial 1  ==  5\r\nmenorFactorial 4  ==  20\r\nmenorFactorial 6  ==  25\r\n<\/pre>\n<pre lang=\"haskell\">\r\nmenorFactorial :: Integer -> Integer\r\nmenorFactorial k = head [n | n <- [1..], cerosDelFactorial n == k]\r\n<\/pre>\n<p>Finalmente definimos la soluci\u00f3n del problema; es decir, el menor n\u00famero natural n tal que n! termina exactamente en 1987 ceros. <\/p>\n<pre lang=\"haskell\">\r\nsolucion :: Integer\r\nsolucion = menorFactorial 1987\r\n<\/pre>\n<p>El c\u00e1lculo de la soluci\u00f3n es<\/p>\n<pre lang=\"text\">\r\nghci> solucion\r\n7960\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado la soluci\u00f3n con Haskell de un problema propuesto para la Olimpiada Internacional de Matem\u00e1ticas de 1987 cuyo enunciado es &#8221;Calcular el menor n\u00famero natural n tal que n! termina exactamente en 1987 ceros.&#8221; Resolverlo con Haskell. Para resolverlo, empezamos definiendo&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[1],"tags":[270,298,200],"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\/2420"}],"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=2420"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2420\/revisions"}],"predecessor-version":[{"id":2717,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2420\/revisions\/2717"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}