{"id":3265,"date":"2013-04-27T09:37:40","date_gmt":"2013-04-27T09:37:40","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3265"},"modified":"2016-01-09T18:58:15","modified_gmt":"2016-01-09T17:58:15","slug":"fracciones-que-son-cuadrados-perfectos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/fracciones-que-son-cuadrados-perfectos\/","title":{"rendered":"Fracciones que son cuadrados perfectos"},"content":{"rendered":"<p><a href=\"http:\/\/goo.gl\/88ZFN\">Nitesh Singh<\/a> ha planteado en <a href=\"http:\/\/goo.gl\/G0dix\">Mathematics Competitions<\/a> el siguiente <a href=\"http:\/\/goo.gl\/qEVQ1\">problema<\/a>:<\/p>\n<blockquote><p>\n\u00bfCu\u00e1ntos n\u00fameros enteros n existen tales que n\/(1450\u2212n) es un cuadrado perfecto?\n<\/p><\/blockquote>\n<p>Vamos a generalizarlo y resolverlo con Haskell. La generalizaci\u00f3n es<\/p>\n<blockquote><p>\nPara cada n\u00famero natural x, calcular los n\u00fameros enteros n tales que n\/(x\u2212n) es  un cuadrado perfecto.\n<\/p><\/blockquote>\n<p>Escribiremos dos formas de resolverlo y compararemos su eficiencia.<\/p>\n<p>Este ejercicio sirve para ilustrar c\u00f3mo el prepocesamiento matem\u00e1tico puede ayudar a mejorar la eficiencia de los programas.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 1\u00aa soluci\u00f3n                                                      --\n-- ---------------------------------------------------------------------\n\n-- Puesto que n\/(x-n) es un cuadrado perfecto, se tiene que 0 \u2264 n < x.\n\n-- (soluciones1 x) es la lista de los n\u00fameros enteros n tales que\n-- n\/(x\u2212n) es un cuadrado perfecto. Por ejemplo,\n--    soluciones1 1450  ==  [0,725,1160,1305,1421,1440,1445]\nsoluciones1 :: Integer -> [Integer]\nsoluciones1 x = \n  [n | n <- [0..x-1], \n       n `rem` (x - n) == 0,\n       esCuadrado (n `div` (x - n))]\n  \n-- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por ejemplo, \n--    esCuadrado  9  ==  True\n--    esCuadrado 10  ==  False\nesCuadrado :: Integer -> Bool\nesCuadrado x =\n  x == y^2\n  where y = floor (sqrt (fromIntegral x))\n        \n-- ---------------------------------------------------------------------\n-- \u00a7 2\u00aa soluci\u00f3n                                                      --\n-- ---------------------------------------------------------------------\n\n-- Puesto que n\/(x-n) es un cuadrado perfecto, existe un k tal que\n--    n\/(x-n) = k^2\n-- Luego,         \n--    n = x * k^2\/(k^2 + 1).     \n-- Adem\u00e1s, como n < x se tiene que k < sqrt(x).        \n\n-- (soluciones2 x) es la lista de los n\u00fameros enteros n tales que\n-- n\/(x\u2212n) es un cuadrado perfecto. Por ejemplo,\n--    soluciones2 1450  ==  [0,725,1160,1305,1421,1440,1445]\nsoluciones2 :: Integer -> [Integer]\nsoluciones2 x =\n  [x * k^2 `div` (k^2 + 1) | k <- [0..c-1], \n                             x * k^2 `rem` (k^2 + 1) == 0]\n  where c = ceiling (sqrt (fromIntegral x))\n        \n-- ---------------------------------------------------------------------\n-- \u00a7 Equivalencia de las soluciones                                   --\n-- ---------------------------------------------------------------------\n        \n-- (prop_equivalencia m) se verifica si para todos los n\u00fameros x entre 0\n-- y m, son iguales (soluciones1 x) y (soluciones2 x). Por ejemplo,          \n--    ghci> prop_equivalencia 2000\n--    True\nprop_equivalencia :: Integer -> Bool\nprop_equivalencia m =\n  and [soluciones1 x == soluciones2 x | x <- [0..m]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Comparaci\u00f3n de la eficiencia                                     --\n-- ---------------------------------------------------------------------\n\n-- La segunda definici\u00f3n es m\u00e1s eficiente como se comprueba en el\n-- siguiente ejemplo:\n--    ghci> length (soluciones1 10000000)\n--    5\n--    (34.39 secs, 1360001588 bytes)\n--    ghci> length (soluciones2 10000000)\n--    5\n--    (0.05 secs, 3098372 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Nitesh Singh ha planteado en Mathematics Competitions el siguiente problema: \u00bfCu\u00e1ntos n\u00fameros enteros n existen tales que n\/(1450\u2212n) es un cuadrado perfecto? Vamos a generalizarlo y resolverlo con Haskell. La generalizaci\u00f3n es Para cada n\u00famero natural x, calcular los n\u00fameros enteros n tales que n\/(x\u2212n) es un cuadrado perfecto. Escribiremos dos formas de resolverlo y&#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":[209,270],"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\/3265"}],"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=3265"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3265\/revisions"}],"predecessor-version":[{"id":5277,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3265\/revisions\/5277"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3265"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3265"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3265"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}