{"id":1046,"date":"2015-02-06T08:48:33","date_gmt":"2015-02-06T06:48:33","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1046"},"modified":"2021-04-25T16:20:53","modified_gmt":"2021-04-25T14:20:53","slug":"menor-numero-triangular-con-mas-de-n-divisores-2015","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-numero-triangular-con-mas-de-n-divisores-2015\/","title":{"rendered":"Menor n\u00famero triangular con m\u00e1s de n divisores"},"content":{"rendered":"<p>La sucesi\u00f3n de los <a href=\"http:\/\/bit.ly\/16xJtKZ\">n\u00fameros triangulares<\/a> se obtiene sumando los n\u00fameros naturales.<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/bit.ly\/1zesZ0M\" width=\"500\" height=\"77\" class=\"alignnone\" \/><\/p>\n<p>As\u00ed, el 7\u00ba n\u00famero triangular es<\/p>\n<pre lang=\"text\">\n   1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. \n<\/pre>\n<p>Los primeros 10 n\u00fameros triangulares son<\/p>\n<pre lang=\"text\">\n   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\n<\/pre>\n<p>Los divisores de los primeros 7 n\u00fameros triangulares son:<\/p>\n<pre lang=\"text\">\n    1: 1\n    3: 1,3\n    6: 1,2,3,6\n   10: 1,2,5,10\n   15: 1,3,5,15\n   21: 1,3,7,21\n   28: 1,2,4,7,14,28\n<\/pre>\n<p>Como se puede observar, 28 es el menor n\u00famero triangular con m\u00e1s de 5 divisores.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   menorTriangularConAlMenosNDivisores :: Int -> Integer\n<\/pre>\n<p>tal que (menorTriangularConAlMenosNDivisores n) es el menor n\u00famero triangular que tiene al menos n divisores. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   menorTriangularConAlMenosNDivisores 5    ==  28\n   menorTriangularConAlMenosNDivisores 50   ==  25200\n   menorTriangularConAlMenosNDivisores 500  ==  76576500\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group)\nimport Data.Numbers.Primes (primes,primeFactors)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmenorTriangularConAlMenosNDivisores1 :: Int -> Integer\nmenorTriangularConAlMenosNDivisores1 n = \n    head [x | x <- triangulares, nDivisores x >= n]\n\n-- triangulares es la sucesi\u00f3n de los n\u00fameros triangulares. Por ejemplo,\n--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]\ntriangulares :: [Integer]\ntriangulares = scanl (+) 1 [2..]\n\n-- (nDivisores x) es el n\u00famero de divisores de x. Por ejemplo,\n--    nDivisores 28  ==  6\nnDivisores :: Integer -> Int\nnDivisores x = \n    1 + length [y | y <- [1..x `div` 2], mod x y == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmenorTriangularConAlMenosNDivisores2 :: Int -> Integer\nmenorTriangularConAlMenosNDivisores2 n = \n    head [x | x <- triangulares, nDivisores2 x >= n]\n\n-- (nDivisores2 x) es el n\u00famero de divisores de x. Por ejemplo,\n--    nDivisores2 28  ==  6\nnDivisores2 :: Integer -> Int\nnDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]    \n\n-- (factoresPrimos n) es la lista de los factores primos de n. Por\n-- ejemplo, \n--    factoresPrimos 28  ==  [2,2,7]\nfactoresPrimos :: Integer -> [Integer]\nfactoresPrimos n = aux n primos\n    where aux n (p:ps) \n              | p*p > n        = [n]\n              | n `mod` p == 0 = p : aux (n `div` p) (p:ps)\n              | otherwise      = aux n ps\n\n-- primos es la lista de los n\u00fameros primos. Por ejemplo,\n--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]\nprimos :: [Integer]\nprimos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]\n\n-- 3\u00aa soluci\u00f3n (usando primes)\n-- ===========================\n\nmenorTriangularConAlMenosNDivisores3 :: Int -> Integer\nmenorTriangularConAlMenosNDivisores3 n = \n    head [x | x <- triangulares, nDivisores3 x >= n]\n\n-- (nDivisores3 x) es el n\u00famero de divisores de x. Por ejemplo,\n--    nDivisores3 28  ==  6\nnDivisores3 :: Integer -> Int\nnDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]    \n\n-- (factoresPrimos3 n) es la lista de los factores primos de n. Por\n-- ejemplo, \n--    factoresPrimos3 28  ==  [2,2,7]\nfactoresPrimos3 n = aux n primes\n  where\n    aux n (p:ps) \n        | p*p > n        = [n]\n        | n `mod` p == 0 = p : aux (n `div` p) (p:ps)\n        | otherwise      = aux n ps\n\n-- 4\u00aa soluci\u00f3n (usando primeFactors)\n-- =================================\n\nmenorTriangularConAlMenosNDivisores4 :: Int -> Integer\nmenorTriangularConAlMenosNDivisores4 n = \n    head [x | x <- triangulares, nDivisores4 x >= n]\n\n-- (nDivisores4 x) es el n\u00famero de divisores de x. Por ejemplo,\n--    nDivisores4 28  ==  6\nnDivisores4 :: Integer -> Int\nnDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]    \n\n-- ---------------------------------------------------------------------\n-- \u00a7 Comparaci\u00f3n de eficiencia                                        --\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    ghci> menorTriangularConAlMenosNDivisores1 50\n--    25200\n--    (1.25 secs, 200236512 bytes)\n--    \n--    ghci> menorTriangularConAlMenosNDivisores2 50\n--    25200\n--    (0.02 secs, 4199904 bytes)\n--    \n--    ghci> menorTriangularConAlMenosNDivisores3 50\n--    25200\n--    (0.03 secs, 6265128 bytes)\n--    \n--    ghci> menorTriangularConAlMenosNDivisores4 50\n--    25200\n--    (0.01 secs, 5753048 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los n\u00fameros naturales. As\u00ed, el 7\u00ba n\u00famero triangular es 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Los primeros 10 n\u00fameros triangulares son 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, &#8230; Los divisores de los primeros&#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":[5],"tags":[8,30,38,13,71,28,89,11,247,173,157,6,78],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1046"}],"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=1046"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1046\/revisions"}],"predecessor-version":[{"id":1082,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1046\/revisions\/1082"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}