{"id":7083,"date":"2022-06-20T06:00:34","date_gmt":"2022-06-20T04:00:34","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7083"},"modified":"2022-06-21T11:54:08","modified_gmt":"2022-06-21T09:54:08","slug":"menor-numero-con-una-cantidad-dada-de-divisores","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-numero-con-una-cantidad-dada-de-divisores\/","title":{"rendered":"Menor n\u00famero con una cantidad dada de divisores"},"content":{"rendered":"<p>El menor n\u00famero con 2 divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) s\u00f3lo tiene 1 divisor (el 1).<\/p>\n<p>El menor n\u00famero con 4 divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).<\/p>\n<p>El menor n\u00famero con 8 divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.<\/p>\n<p>El menor n\u00famero con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   menor :: Integer -> Integer\n<\/pre>\n<p>tal que <code>(menor n)<\/code> es el menor n\u00famero con 2^n divisores. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   menor 1  ==  2\n   menor 2  ==  6\n   menor 3  ==  24\n   menor 4  ==  120\n   length (show (menor (4*10^4)))  ==  207945\n<\/pre>\n<p>Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).<\/p>\n<p><strong>Nota<\/strong>: Este ejercicio est\u00e1 basado en el <a href=\"https:\/\/bit.ly\/2LhS0w8\">problema N1<\/a> de la Olimp\u00edada Internacional de Matem\u00e1ticas (IMO) del 2011.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List           (genericLength, genericTake, group)\nimport Data.Numbers.Primes (primeFactors, primes)\nimport Test.QuickCheck     (Positive (Positive), maxSize, stdArgs,\n                            quickCheck, quickCheckWith)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmenor1 :: Integer -> Integer\nmenor1 n =\n  head [x | x <- [1..], numeroDivisores x == 2^n]\n\n-- (numeroDivisores n) es el n\u00famero de divisores de n. Por ejemplo, \n--    numeroDivisores 12  ==  6\nnumeroDivisores :: Integer -> Integer\nnumeroDivisores =\n  genericLength . divisores\n\n-- (divisores x) es la lista de los divisores de x. Por ejemplo,\n--    divisores 12  ==  [1,3,2,6,4,12]\n--    divisores 25  ==  [1,5,25]\ndivisores :: Integer -> [Integer]\ndivisores n =\n  [x | x <- [1..n], n `rem` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmenor2 :: Integer -> Integer\nmenor2 n =\n  head [x | x <- [1..], numeroDivisores2 x == 2^n]\n\nnumeroDivisores2 :: Integer -> Integer\nnumeroDivisores2 =\n  product . map ((+1) . genericLength) . group . primeFactors\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmenor3 :: Integer -> Integer\nmenor3 n = product (genericTake n potencias)\n\n-- potencias es la sucesi\u00f3n de las potencias de la forma p^(2^k),\n-- donde p es un n\u00famero primo y k es un n\u00famero natural, ordenadas de\n-- menor a mayor. Por ejemplo,\n--    take 14 potencias    ==  [2,3,4,5,7,9,11,13,16,17,19,23,25,29]\npotencias :: [Integer]\npotencias = 2 : mezcla (tail primes) (map (^2) potencias)\n\n-- (mezcla xs ys) es la lista obtenida mezclando las dos listas xs e ys,\n-- que se suponen ordenadas y disjuntas. Por ejemplo,\n--    \u03bb> take 15 (mezcla [2^n | n <- [1..]] [3^n | n <- [1..]])\n--    [2,3,4,8,9,16,27,32,64,81,128,243,256,512,729]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)\n                     | x > y = y : mezcla (x:xs) ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_menor :: Positive Integer -> Bool\nprop_menor (Positive n) =\n  all (== menor1 n)\n      [menor2 n,\n       menor3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=5}) prop_menor\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--   \u03bb> menor 8\n--   1081080\n--   (47.69 secs, 94,764,856,352 bytes)\n--   \u03bb> menor2 8\n--   1081080\n--   (36.17 secs, 94,764,856,368 bytes)\n--   \u03bb> menor3 8\n--   1081080\n--   (0.00 secs, 116,960 bytes)\n\n-- Definici\u00f3n de menor\n-- ===================\n\n-- En lo que sigue, usaremos menor3 como menor.\nmenor :: Integer -> Integer\nmenor = menor3\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_menor_divide :: Positive Integer -> Bool\nprop_menor_divide (Positive n) =\n  menor (n+1) `mod` menor n == 0\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_menor_divide\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Menor_numero_con_una_cantidad_dada_de_divisores.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El menor n\u00famero con 2 divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) s\u00f3lo tiene 1 divisor (el 1). El menor n\u00famero con 4 divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores&#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":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7083"}],"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=7083"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7083\/revisions"}],"predecessor-version":[{"id":7084,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7083\/revisions\/7084"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7083"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7083"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}