{"id":6391,"date":"2021-05-14T06:00:11","date_gmt":"2021-05-14T04:00:11","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6391"},"modified":"2021-05-21T10:44:32","modified_gmt":"2021-05-21T08:44:32","slug":"numeros-consecutivos-con-factorizacion-con-exponentes-impares","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-consecutivos-con-factorizacion-con-exponentes-impares\/","title":{"rendered":"N\u00fameros consecutivos con factorizaci\u00f3n con exponentes impares"},"content":{"rendered":"<p>El enunciado del problema B.5 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  Los n\u00fameros naturales 22, 23, y 24 tienen la siguiente propiedad: los exponentes de los factores primos de su descomposici\u00f3n son todos impares (22 = 2\u00b9\u00b711\u00b9, 23 = 23\u00b9, 24 = 2\u00b3\u00b73\u00b9)<\/p>\n<p>  \u00bfCu\u00e1l es el mayor n\u00famero de naturales consecutivos que pueden tener esa propiedad?. Raz\u00f3nese la contestaci\u00f3n.\n<\/p><\/blockquote>\n<p>Definir la lista<\/p>\n<pre lang=\"text\">\n   consecutivosExponentesImpares :: [[Integer]]\n<\/pre>\n<p>cuyos elementos sean las sucesiones maximales de n\u00fameros enteros positivos tales que los exponentes de los factores primos de su descomposici\u00f3n son todos impares. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 7 consecutivosExponentesImpares\n   [[1,2,3],[5,6,7,8],[10,11],[13,14,15],[17],[19],[21,22,23,24]]\n   \u03bb> consecutivosExponentesImpares !! (10^4)\n   [43030,43031,43032,43033,43034,43035]\n<\/pre>\n<p>Usando la funci\u00f3n consecutivosExponentesImpares conjeturar la respuesta a la pregunta del problema y comprobarla con QuickCheck.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck (Property, (==>), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nconsecutivosExponentesImpares :: [[Integer]]\nconsecutivosExponentesImpares =\n  consecutivosExponentesImparesDesde 1 :\n  [consecutivosExponentesImparesDesde n | n <- [1..],\n                                          not (exponentesImpares (n-1)),\n                                          exponentesImpares n]\n\n-- (consecutivosExponentesImparesDesde n) es la sucesi\u00f3n maximal de\n-- n\u00fameros enteros positivos a partir de n tales que los exponentes de\n-- los factores primos de su descomposici\u00f3n son todos impares. Por\n-- ejemplo,\n--    consecutivosExponentesImparesDesde 1  ==  [1,2,3]\n--    consecutivosExponentesImparesDesde 4  ==  []\n--    consecutivosExponentesImparesDesde 5  ==  [5,6,7,8]\nconsecutivosExponentesImparesDesde :: Integer -> [Integer]\nconsecutivosExponentesImparesDesde n\n  | exponentesImpares n = n : consecutivosExponentesImparesDesde (n+1)\n  | otherwise           = []\n\n-- (exponentesImpares n) se verifica si los exponentes de los factores\n-- primos de su descomposici\u00f3n son todos impares. Por ejemplo,\n--    exponentesImpares 4  ==  False\n--    exponentesImpares 6  ==  True\nexponentesImpares :: Integer -> Bool\nexponentesImpares n = all odd (exponentes n)\n\n-- (exponentes n) es la lista de los exponentes de la factorizaci\u00f3n\n-- prima de n. Por ejemplo,\n--    exponentes 4  ==  [2]\n--    exponentes 6  ==  [1,1]\n--    exponentes 1200  ==  [4,1,2]\nexponentes :: Integer -> [Int]\nexponentes n = map length (group (primeFactors n))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nconsecutivosExponentesImpares2 :: [[Integer]]\nconsecutivosExponentesImpares2 = aux 1\n  where aux n | exponentesImpares n = xs : aux (1 + last xs)\n              | otherwise           = aux (n+1)\n          where xs = consecutivosExponentesImparesDesde n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_consecutivosExponentesImpares :: Int -> Property\nprop_consecutivosExponentesImpares n =\n  n > 0 ==>\n  consecutivosExponentesImpares !! n == consecutivosExponentesImpares2 !! n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_consecutivosExponentesImpares\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> consecutivosExponentesImpares !! (5*10^4)\n--    [214917,214918,214919,214920,214921,214922,214923]\n--    (4.95 secs, 14,329,413,944 bytes)\n--    \u03bb> consecutivosExponentesImpares2 !! (5*10^4)\n--    [214917,214918,214919,214920,214921,214922,214923]\n--    (5.29 secs, 15,103,460,488 bytes)\n\n-- Respuesta a la pregunta del problema\n-- ====================================\n\n-- A partir del siguiente c\u00e1lculo\n--    \u03bb> maximum [length xs | xs <- take (10^4) consecutivosExponentesImpares]\n--    7\n-- se puede conjeturar que el mayor n\u00famero de naturales consecutivos que pueden\n-- tener la propiedad es 7. Por el c\u00e1lculo, se sabe que es mayor o igual\n-- que 7. Falta por comprobar que es menor o igual que 7; es decir,\nprop_maximoConsecutivosExponentesImpares :: Int -> Property\nprop_maximoConsecutivosExponentesImpares n =\n  n >= 0 ==>\n  length (consecutivosExponentesImpares !! n) <= 7\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maximoConsecutivosExponentesImpares\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 B.5 de la Fase Local de la Olimpiada Matem\u00e1tica Espa\u00f1ola del 2006 es Los n\u00fameros naturales 22, 23, y 24 tienen la siguiente propiedad: los exponentes de los factores primos de su descomposici\u00f3n son todos impares (22 = 2\u00b9\u00b711\u00b9, 23 = 23\u00b9, 24 = 2\u00b3\u00b73\u00b9) \u00bfCu\u00e1l es el mayor n\u00famero de&#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\/6391"}],"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=6391"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6391\/revisions"}],"predecessor-version":[{"id":6481,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6391\/revisions\/6481"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6391"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6391"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6391"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}