{"id":6398,"date":"2021-05-17T06:00:29","date_gmt":"2021-05-17T04:00:29","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6398"},"modified":"2021-05-24T10:18:09","modified_gmt":"2021-05-24T08:18:09","slug":"cuadrado-mas-primo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/cuadrado-mas-primo\/","title":{"rendered":"Cuadrado m\u00e1s primo"},"content":{"rendered":"<p>El enunciado del problema C2 de la <a href=\"https:\/\/bit.ly\/3xKhMw6\">Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2006<\/a> es<\/p>\n<blockquote><p>\n  \u00bfExiste un conjunto infinito de n\u00fameros naturales que NO se pueden representar en la forma n\u00b2+p, siendo n natural y p primo? Raz\u00f3nese la contestaci\u00f3n.\n<\/p><\/blockquote>\n<p>Definir la lista<\/p>\n<pre lang=\"text\">\n   noSonCuadradoMasPrimo :: [Integer]\n<\/pre>\n<p>cuyos elementos son los n\u00fameros que no se pueden escribir como un cuadrado m\u00e1s un primo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 15 noSonCuadradoMasPrimo\n   [1,10,25,34,58,64,85,91,121,130,169,196,214,226,289]\n   \u03bb> noSonCuadradoMasPrimo2 !! 200\n   78961\n   <\/pre>\n<p>En la lista no est\u00e1 el 2 (porque 2 = 0\u00b2+2), el 3 (porque 3 = 1\u00b2+2), el 4 (porque 4 = 0\u00b2+4) ni el 11 (porque 11 = 3\u00b2+2).<\/p>\n<p>Comprobar con QuickCheck que noSonCuadradoMasPrimo es infinita.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes, isPrime)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnoSonCuadradoMasPrimo :: [Integer]\nnoSonCuadradoMasPrimo =\n  filter (not . esCuadradoMasPrimo) [1..]\n\n-- (esCuadradoMasPrimo n) se verifica si n se puede escribir como un\n-- cuadrado m\u00e1s un primo. Por ejemplo,\n--    esCuadradoMasPrimo 11  ==  True\n--    esCuadradoMasPrimo 10  ==  False\nesCuadradoMasPrimo :: Integer -> Bool\nesCuadradoMasPrimo n =\n  or [esCuadrado (n - p) | p <- takeWhile (<= n) primes]\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-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnoSonCuadradoMasPrimo2 :: [Integer]\nnoSonCuadradoMasPrimo2 =\n  filter (not . esCuadradoMasPrimo2) [1..]\n\n-- (esCuadradoMasPrimo2 n) se verifica si n se puede escribir como un\n-- cuadrado m\u00e1s un primo. Por ejemplo,\n--    esCuadradoMasPrimo2 11  ==  True\n--    esCuadradoMasPrimo2 10  ==  False\nesCuadradoMasPrimo2 :: Integer -> Bool\nesCuadradoMasPrimo2 n =\n  or [isPrime (n - m) | m <- takeWhile (<= n) cuadrados]\n\n-- cuadrados es la lista de los cuadrados de los n\u00fameros naturales. Por\n-- ejemplo,\n--    take 10 cuadrados  ==  [0,1,4,9,16,25,36,49,64,81]\ncuadrados :: [Integer]\ncuadrados = map (^2) [0..]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> take 50 noSonCuadradoMasPrimo == take 50 noSonCuadradoMasPrimo2\n--    True\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> noSonCuadradoMasPrimo !! 70\n--    8649\n--    (12.42 secs, 13,289,896,304 bytes)\n--    \u03bb> noSonCuadradoMasPrimo2 !! 70\n--    8649\n--    (0.23 secs, 650,843,816 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_infinitud :: Integer -> Bool\nprop_infinitud n =\n  not (null (dropWhile (<= n) noSonCuadradoMasPrimo2))\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_infinitud\n--    +++ OK, passed 100 tests.\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 C2 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2006 es \u00bfExiste un conjunto infinito de n\u00fameros naturales que NO se pueden representar en la forma n\u00b2+p, siendo n natural y p primo? Raz\u00f3nese la contestaci\u00f3n. Definir la lista noSonCuadradoMasPrimo :: [Integer] cuyos elementos son los n\u00fameros que no&#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\/6398"}],"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=6398"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6398\/revisions"}],"predecessor-version":[{"id":6484,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6398\/revisions\/6484"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}