Árbol de divisores
Se dice que a es un divisor propio maximal de un número b si a es un divisor de b distinto de b y no existe ningún número c tal que a < c < 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.
El árbol de los divisores de un número x es el árbol que tiene como raíz el número x y cada nodo tiene como hijos sus divisores propios maximales. Por ejemplo, el árbol de divisores de 30 es
1 2 3 4 5 6 7 8 9 |
30 /|\ / | \ / | \ / | \ / | \ 6 10 15 / \ / \ / \ 2 3 2 5 3 5 |
Usando el tipo de dato
1 2 |
data Arbol = N Integer [Arbol] deriving (Eq, Show) |
el árbol anterior se representa por
1 2 3 4 5 6 7 8 9 10 |
N 30 [N 6 [N 2 [N 1 []], N 3 [N 1 []]], N 10 [N 2 [N 1 []], N 5 [N 1 []]], N 15 [N 3 [N 1 []], N 5 [N 1 []]]] |
Definir las funciones
1 2 |
arbolDivisores :: Integer -> Arbol nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer |
tales que
- (arbolDivisores x) es el árbol de los divisores del número x. Por ejemplo,
1 2 3 4 |
λ> arbolDivisores 30 N 30 [N 6 [N 2 [N 1 []],N 3 [N 1 []]], N 10 [N 2 [N 1 []],N 5 [N 1 []]], N 15 [N 3 [N 1 []],N 5 [N 1 []]]] |
- (nOcurrenciasArbolDivisores x y) es el número de veces que aparece el número x en el árbol de los divisores del número y. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 |
nOcurrenciasArbolDivisores 3 30 == 2 nOcurrenciasArbolDivisores 6 30 == 1 nOcurrenciasArbolDivisores 30 30 == 1 nOcurrenciasArbolDivisores 1 30 == 6 nOcurrenciasArbolDivisores 9 30 == 0 nOcurrenciasArbolDivisores 2 (product [1..10]) == 360360 nOcurrenciasArbolDivisores 3 (product [1..10]) == 180180 nOcurrenciasArbolDivisores 5 (product [1..10]) == 90090 nOcurrenciasArbolDivisores 7 (product [1..10]) == 45045 nOcurrenciasArbolDivisores 6 (product [1..10]) == 102960 nOcurrenciasArbolDivisores 10 (product [1..10]) == 51480 nOcurrenciasArbolDivisores 14 (product [1..10]) == 25740 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import Data.Numbers.Primes (primeFactors) import Data.List (genericLength, group, nub) data Arbol = N Integer [Arbol] deriving (Eq, Show) -- Definición de arbolDivisores -- ============================ arbolDivisores :: Integer -> Arbol arbolDivisores x = N x (map arbolDivisores (divisoresPropiosMaximales x)) -- (divisoresPropiosMaximales x) es la lista de los divisores propios -- maximales de x. Por ejemplo, -- divisoresPropiosMaximales 30 == [6,10,15] -- divisoresPropiosMaximales 420 == [60,84,140,210] -- divisoresPropiosMaximales 7 == [1] divisoresPropiosMaximales :: Integer -> [Integer] divisoresPropiosMaximales x = reverse [x `div` y | y <- nub (primeFactors x)] -- Definición de nOcurrenciasArbolDivisores -- ======================================== nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer nOcurrenciasArbolDivisores x y = nOcurrencias x (arbolDivisores y) -- (nOcurrencias x a) es el número de veces que aprece x en el árbol -- a. Por ejemplo, -- nOcurrencias 3 (arbolDivisores 30) == 2 nOcurrencias :: Integer -> Arbol -> Integer nOcurrencias x (N y []) | x == y = 1 | otherwise = 0 nOcurrencias x (N y zs) | x == y = 1 + sum [nOcurrencias x z | z <- zs] | otherwise = sum [nOcurrencias x z | z <- zs] |
Pensamiento
«¿Dónde está la utilidad
de nuestras utilidades?
Volvamos a la verdad:
vanidad de vanidades.»Antonio Machado