{"id":6324,"date":"2021-04-29T06:00:01","date_gmt":"2021-04-29T04:00:01","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6324"},"modified":"2021-05-06T07:42:35","modified_gmt":"2021-05-06T05:42:35","slug":"orbita-con-raiz-entera-ome1997-p4","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/orbita-con-raiz-entera-ome1997-p4\/","title":{"rendered":"\u00d3rbita con ra\u00edz entera (OME1997 P4)"},"content":{"rendered":"<p>El enunciado del <a href=\"https:\/\/bit.ly\/3aqnPMq\">problema 4 de la OME (Olimpiada Matem\u00e1tica Espa\u00f1ola) del 1997<\/a> es<\/p>\n<blockquote><p>\n  Sea p un n\u00famero primo. Determinar todos los enteros k tales que sqrt(k\u00b2 &#8211; k*p) es natural.\n<\/p><\/blockquote>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   orbita        :: Integer -> [Integer]\n   orbitaDePrimo :: Integer -> [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(orbita n) es la lista de todos los enteros k tales que sqrt(k\u00b2 &#8211; k*n) es natural. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     take 4  (orbita 6)   == [0,-2,6,8]\n     take 5  (orbita 36)  == [0,-12,36,48,-64]\n     take 6  (orbita 9)   == [0,-3,9,12,-16,25]\n     take 8  (orbita 27)  == [0,-9,27,36,-48,75,-169,196]\n     take 10 (orbita 111) == [0,-37,111,148,-289,400,-972,1083,-3025,3136]\n<\/pre>\n<ul>\n<li>(orbitaDePrimo p) es la lista de todos los enteros k tales que sqrt(k\u00b2 &#8211; k*p) es natural, suponiendo que p es un n\u00famero primo. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     orbitaDePrimo 5                  == [0,-4,5,9]\n     orbitaDePrimo (primes !! (10^6)) == [0,15485867,-59953011442489,59953026928356]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\n\norbita :: Integer -> [Integer]\norbita n =\n  [k | k <- enteros,\n       k^2 - k*n >= 0,\n       esCuadrado (k^2 - k*n)]\n\n-- entero es la lista de los n\u00fameros enteros. Por ejemplo,\n--    \u03bb> take 20 enteros\n--    [0,-1,1,-2,2,-3,3,-4,4,-5,5,-6,6,-7,7,-8,8,-9,9,-10]\nenteros :: [Integer]\nenteros = 0 : concat [[-n,n] | n <- [1..]]\n\n-- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por\n-- ejemplo,\n--    esCuadrado 16  ==  True\n--    esCuadrado 27  ==  False\nesCuadrado :: Integer -> Bool\nesCuadrado x =\n  (raizEntera x)^2 == x\n\n-- (raizEntera x) es el mayor entero cuyo cuadrado es menor o igual que\n-- x. Por ejemplo,\n--    raizEntera 16  ==  4\n--    raizEntera 27  ==  5\nraizEntera :: Integer -> Integer\nraizEntera x = aux (1,x)\n    where aux (a,b) | d == x    = c\n                    | c == a    = c\n                    | d < x     = aux (c,b)\n                    | otherwise = aux (a,c)\n              where c = (a+b) `div` 2\n                    d = c^2\n\n-- 1\u00aa definici\u00f3n de orbitaDePrimo\n-- ==============================\n\norbitaDePrimo1 :: Integer -> [Integer]\norbitaDePrimo1 2 = take 2 (orbita 2)\norbitaDePrimo1 p = take 4 (orbita p)\n\n-- 2\u00aa definici\u00f3n de orbitaDePrimo\n-- ==============================\n\n-- Basada en los siguientes c\u00e1lculos\n--    orbitaDePrimo1 2  == [0,2]\n--    orbitaDePrimo1 3  == [0,-1,3,4]\n--    orbitaDePrimo1 5  == [0,-4,5,9]\n--    orbitaDePrimo1 7  == [0, 7,  -9, 16]\n--    orbitaDePrimo1 11 == [0,11, -25, 36]\n--    orbitaDePrimo1 13 == [0,13, -36, 49]\n--    orbitaDePrimo1 17 == [0,17, -64, 81]\n--    orbitaDePrimo1 19 == [0,19, -81,100]\n--    orbitaDePrimo1 23 == [0,23,-121,144]\n\norbitaDePrimo2 :: Integer -> [Integer]\norbitaDePrimo2 p\n  | p == 2    = [0,2]\n  | p <= 5    = [0, -((p-1) `div` 2)^2, p, ((p+1) `div` 2)^2]\n  | otherwise = [0, p, -((p-1) `div` 2)^2, ((p+1) `div` 2)^2]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> and [orbitaDePrimo1 n == orbitaDePrimo2 n | n <- take 30 primes]\n--    True\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> orbitaDePrimo1 (primes !! 100)\n--    [0,547,-74529,75076]\n--    (4.94 secs, 4,471,368,256 bytes)\n--    \u03bb> orbitaDePrimo2 (primes !! 100)\n--    [0,547,-74529,75076]\n--    (0.01 secs, 302,096 bytes)\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El enunciado del problema 4 de la OME (Olimpiada Matem\u00e1tica Espa\u00f1ola) del 1997 es Sea p un n\u00famero primo. Determinar todos los enteros k tales que sqrt(k\u00b2 &#8211; k*p) es natural. Definir las funciones orbita :: Integer -> [Integer] orbitaDePrimo :: Integer -> [Integer] tales que (orbita n) es la lista de todos los enteros&#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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6324"}],"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=6324"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6324\/revisions"}],"predecessor-version":[{"id":6405,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6324\/revisions\/6405"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6324"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6324"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}