{"id":4443,"date":"2018-12-21T06:00:49","date_gmt":"2018-12-21T04:00:49","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4443"},"modified":"2018-12-28T08:51:42","modified_gmt":"2018-12-28T06:51:42","slug":"arbol-de-divisores","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arbol-de-divisores\/","title":{"rendered":"\u00c1rbol de divisores"},"content":{"rendered":"<p>Se dice que a es un divisor propio maximal de un n\u00famero b si a es un divisor de b distinto de b y no existe ning\u00fan n\u00famero c tal que a &lt; c &lt; b, a es un divisor de c y c es un divisor de b. Por ejemplo, 15 es un divisor propio maximal de 30, pero 5 no lo es.<\/p>\n<p>El \u00e1rbol de los divisores de un n\u00famero x es el \u00e1rbol que tiene como ra\u00edz el n\u00famero x y cada nodo tiene como hijos sus divisores propios maximales. Por ejemplo, el \u00e1rbol de divisores de 30 es<\/p>\n<pre lang=\"text\">\n          30\n          \/|\\\n         \/ | \\\n        \/  |  \\\n       \/   |   \\\n      \/    |    \\\n     6    10    15\n    \/ \\   \/ \\   \/ \\\n   2   3 2   5 3   5\n<\/pre>\n<p>Usando el tipo de dato<\/p>\n<pre lang=\"text\">\n   data Arbol = N Integer [Arbol]\n     deriving (Eq, Show)\n<\/pre>\n<p>el \u00e1rbol anterior se representa por<\/p>\n<pre lang=\"text\">\n   N 30\n     [N 6\n        [N 2 [N 1 []],\n         N 3 [N 1 []]],\n      N 10\n        [N 2 [N 1 []],\n         N 5 [N 1 []]],\n      N 15\n        [N 3 [N 1 []],\n         N 5 [N 1 []]]]\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   arbolDivisores             :: Integer -> Arbol\n   nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(arbolDivisores x) es el \u00e1rbol de los divisores del n\u00famero x. Por ejemplo,  <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> arbolDivisores 30\n     N 30 [N 6  [N 2 [N 1 []],N 3 [N 1 []]],\n           N 10 [N 2 [N 1 []],N 5 [N 1 []]],\n           N 15 [N 3 [N 1 []],N 5 [N 1 []]]]\n<\/pre>\n<ul>\n<li>(nOcurrenciasArbolDivisores x y) es el n\u00famero de veces que aparece el n\u00famero x en el \u00e1rbol de los divisores del n\u00famero y. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nOcurrenciasArbolDivisores  3 30  ==  2\n     nOcurrenciasArbolDivisores  6 30  ==  1\n     nOcurrenciasArbolDivisores 30 30  ==  1\n     nOcurrenciasArbolDivisores  1 30  ==  6\n     nOcurrenciasArbolDivisores  9 30  ==  0\n     nOcurrenciasArbolDivisores  2 (product [1..10])  ==  360360\n     nOcurrenciasArbolDivisores  3 (product [1..10])  ==  180180\n     nOcurrenciasArbolDivisores  5 (product [1..10])  ==  90090\n     nOcurrenciasArbolDivisores  7 (product [1..10])  ==  45045\n     nOcurrenciasArbolDivisores  6 (product [1..10])  ==  102960\n     nOcurrenciasArbolDivisores 10 (product [1..10])  ==  51480\n     nOcurrenciasArbolDivisores 14 (product [1..10])  ==  25740\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primeFactors)\nimport Data.List (genericLength, group, nub)\n\ndata Arbol = N Integer [Arbol]\n  deriving (Eq, Show)\n\n-- Definici\u00f3n de arbolDivisores\n-- ============================\n\narbolDivisores :: Integer -> Arbol\narbolDivisores x =\n  N x (map arbolDivisores (divisoresPropiosMaximales x))\n\n-- (divisoresPropiosMaximales x) es la lista de los divisores propios\n-- maximales de x. Por ejemplo,\n--    divisoresPropiosMaximales 30   ==  [6,10,15]\n--    divisoresPropiosMaximales 420  ==  [60,84,140,210]\n--    divisoresPropiosMaximales 7    ==  [1]\ndivisoresPropiosMaximales :: Integer -> [Integer]\ndivisoresPropiosMaximales x =\n  reverse [x `div` y | y <- nub (primeFactors x)]\n\n-- Definici\u00f3n de nOcurrenciasArbolDivisores\n-- ========================================\n  \nnOcurrenciasArbolDivisores :: Integer -> Integer -> Integer\nnOcurrenciasArbolDivisores x y =\n  nOcurrencias x (arbolDivisores y)\n\n-- (nOcurrencias x a) es el n\u00famero de veces que aprece x en el \u00e1rbol\n-- a. Por ejemplo,\n--    nOcurrencias 3 (arbolDivisores 30)  ==  2\nnOcurrencias :: Integer -> Arbol -> Integer\nnOcurrencias x (N y [])\n  | x == y    = 1\n  | otherwise = 0\nnOcurrencias x (N y zs)\n  | x == y    = 1 + sum [nOcurrencias x z | z <- zs]\n  | otherwise = sum [nOcurrencias x z | z <- zs]\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\"\u00bfD\u00f3nde est\u00e1 la utilidad<br \/>\nde nuestras utilidades?<br \/>\nVolvamos a la verdad:<br \/>\nvanidad de vanidades.\"<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Se dice que a es un divisor propio maximal de un n\u00famero b si a es un divisor de b distinto de b y no existe ning\u00fan n\u00famero c tal que a &lt; c &lt; b, a es un divisor de c y c es un divisor de b. Por ejemplo, 15 es un divisor&#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":[4],"tags":[269,8,30,10,24,11,247,6,32,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4443"}],"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=4443"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4443\/revisions"}],"predecessor-version":[{"id":4484,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4443\/revisions\/4484"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4443"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4443"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4443"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}