{"id":2333,"date":"2012-11-20T20:34:36","date_gmt":"2012-11-20T20:34:36","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2333"},"modified":"2013-03-08T05:47:38","modified_gmt":"2013-03-08T05:47:38","slug":"i1m2012-ultimo-digito-del-producto-de-numeros-de-fermat","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ultimo-digito-del-producto-de-numeros-de-fermat\/","title":{"rendered":"I1M2012: \u00daltimo d\u00edgito del producto de n\u00fameros de Fermat"},"content":{"rendered":"

En la segunda parte de la clase de hoy de 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 (IMO) de 1971. Su enunciado es<\/p>\n

\nSea \"x_n y sea \"m\" el producto de \"x_2,. Calcular el \u00faltimo d\u00edgito de \"m\".\n<\/p><\/blockquote>\n

La primera definici\u00f3n es la traducci\u00f3n directa del enunciado<\/p>\n

\r\nsol1 :: Integer\r\nsol1 = ultimo (product [x n | n <- [2..1971]])\r\n<\/pre>\n
donde (x n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n<\/p>\n
\r\nx :: Int -> Integer \r\nx n = 2^(2^n) + 1 \r\n<\/pre>\n
y (ultimo x) es el \u00faltimo d\u00edgito de x<\/p>\n
\r\nultimo :: Integer -> Integer\r\nultimo x = rem x 10\r\n<\/pre>\n
Aunque la primera soluci\u00f3n es simple, tiene un inconveniente: Haskell no puede calcular n\u00fameros tan grandes. Una estrategia para resolverlo es considerar casos menores y buscar alguna regularidad. Para ello, generalizamos la primera soluci\u00f3n sustituyendo 1971 por una variable. <\/p>\n
\r\nsol2 :: Int -> Integer\r\nsol2 a = ultimo (product [x n | n <- [2..a]])\r\n<\/pre>\n
Con la 2\u00aa definici\u00f3n calculamos el \u00faltimo d\u00edgito de los primeros productos <\/p>\n
\r\nghci> [sol2 a | a <- [2..20]] \r\n[7,9,3,1,7,9,3,1,7,9,3,1,7,9,3,1,7,9,3]\r\n<\/pre>\n
Se observa que el resultado est\u00e1 formado por la repetici\u00f3n de los n\u00fameros 7, 9, 3 y 1. A partir de la observaci\u00f3n conjeturamos una nueva definici\u00f3n<\/p>\n
\r\nsol3 :: Int -> Integer\r\nsol3 a | b == 2 = 7\r\n       | b == 3 = 9\r\n       | b == 0 = 3\r\n       | b == 1 = 1\r\n       where b = rem a 4\r\n<\/pre>\n
Podemos comprobar, para peque\u00f1os valores, que las 2 definiciones son equivalentes <\/p>\n
\r\nghci> [sol2 a | a <- [2..20]] == [sol3 a | a <- [2..20]] \r\nTrue\r\n<\/pre>\n
Adem\u00e1s, con la 3\u00aa definici\u00f3n se puede calcular la soluci\u00f3n del problema original<\/p>\n
\r\nghci> sol3 1971\r\n9\r\n<\/pre>\n
es decir, el \u00faltimo d\u00edgito del producto \"x_2x_3 es 9.<\/p>\n
Para justificar la soluci\u00f3n, hay que demostrar que la definici\u00f3n sol3 es correcta; es decir, que los \u00faltimos d\u00edgitos de los productos forman la sucesi\u00f3n 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, ... Para ello, observamos el \u00faltimo d\u00edgito de los \"x_n\"<\/p>\n
\r\nghci> [ultimo (x n) | n <- [2..20]]\r\n[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]\r\n<\/pre>\n
Se observa que todos son 7. Esto justifica la sucesi\u00f3n de los productos, ya que cada t\u00e9rmino es el \u00faltimo d\u00edgito del producto del anterior por 7. Adem\u00e1s, permite una nueva definici\u00f3n de la soluci\u00f3n por recursi\u00f3n<\/p>\n
\r\nsol4 :: Int -> Integer\r\nsol4 a | a == 2    = 7\r\n       | otherwise = ultimo (7 * sol4 (a-1))\r\n<\/pre>\n
Podemos comprobar, para peque\u00f1os valores, que es equivalente a la anterior<\/p>\n
\r\nghci> [sol3 a | a <- [2..20]] == [sol4 a | a <- [2..20]] \r\nTrue\r\n<\/pre>\n
Para terminar, s\u00f3lo queda demostrar que si \"n>1\", entonces el \u00faltimo d\u00edgito de \"2^{2^n} es 7 o, equivalentemente, que el \u00faltimo d\u00edgito de \"2^{2^n}\" es 6. Lo que se tiene ya que \"2^{2^n}. Adem\u00e1s, como \"n>1\" se tiene que \"2^{n-1}\" es un n\u00famero par mayor que 0 y, por tanto, el \u00faltimo d\u00edgito de \"4^{2^{n-1}}\" es 6.<\/p>\n","protected":false},"excerpt":{"rendered":"
En la segunda parte de 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 (IMO) de 1971. Su enunciado es Sea y sea el producto de . Calcular el \u00faltimo d\u00edgito de . La primera definici\u00f3n…<\/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\/2333"}],"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=2333"}],"version-history":[{"count":10,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2333\/revisions"}],"predecessor-version":[{"id":2744,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2333\/revisions\/2744"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}