Árbol de divisores

PorJosé A. Alonso 21-diciembre-201828-diciembre-2018

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

          30
          /|\
         / | \
        /  |  \
       /   |   \
      /    |    \
     6    10    15
    / \   / \   / \
   2   3 2   5 3   5

/|\

/ | \

6 10 15

/ \ / \ / \

2 3 2 5 3 5

Usando el tipo de dato

   data Arbol = N Integer [Arbol]
     deriving (Eq, Show)

1 2	data Arbol = N Integer [Arbol] deriving (Eq, Show)

el árbol anterior se representa por

   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 []]]]

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

   arbolDivisores             :: Integer -> Arbol
   nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

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,

     λ> 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 []]]]

λ> 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,

     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

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

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]

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

5 Comentarios

import Data.List (nub, genericLength)
import Data.Numbers.Primes (primeFactors)
 
arbolDivisores :: Integer -> Arbol
arbolDivisores n =
  N n [arbolDivisores x | x <- divisoresPropiosMaximales n]

divisoresPropiosMaximales :: Integer -> [Integer]
divisoresPropiosMaximales x =
  [div x y | y <- (reverse . nub . primeFactors) x]
 
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x n =
  nOcurrenciasArbolDivisoresAux x (arbolDivisores n) 
 
nOcurrenciasArbolDivisoresAux :: Integer -> Arbol -> Integer
nOcurrenciasArbolDivisoresAux x (N n xss)
  | x == n    = 1 + sum [nOcurrenciasArbolDivisoresAux x a | a <- xss] 
  | otherwise = sum [nOcurrenciasArbolDivisoresAux x a | a <- xss]

import Data.List (nub, genericLength)

import Data.Numbers.Primes (primeFactors)

arbolDivisores :: Integer -> Arbol

arbolDivisores n =

N n [arbolDivisores x | x <- divisoresPropiosMaximales n]

divisoresPropiosMaximales :: Integer -> [Integer]

divisoresPropiosMaximales x =

[div x y | y <- (reverse . nub . primeFactors) x]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

nOcurrenciasArbolDivisores x n =

nOcurrenciasArbolDivisoresAux x (arbolDivisores n)

nOcurrenciasArbolDivisoresAux :: Integer -> Arbol -> Integer

nOcurrenciasArbolDivisoresAux x (N n xss)

| x == n = 1 + sum [nOcurrenciasArbolDivisoresAux x a | a <- xss]

| otherwise = sum [nOcurrenciasArbolDivisoresAux x a | a <- xss]

Responder

import Data.List
import Data.Numbers.Primes

arbolDivisores :: Integer -> Arbol
arbolDivisores x =
  N x (map arbolDivisores (reverse (divisoresPropiosMaximales x)))

divisoresPropiosMaximales :: Integer -> [Integer]
divisoresPropiosMaximales x =
  [ x `div` y | y <- nub (primeFactors x)]
 
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores y x = nAux y (arbolDivisores x) 

nAux :: Integer -> Arbol -> Integer
nAux x (N n xs) | x == n    = 1 + sum (map (nAux x) xs) 
                | otherwise = sum (map (nAux x) xs)

import Data.List

import Data.Numbers.Primes

arbolDivisores :: Integer -> Arbol

arbolDivisores x =

N x (map arbolDivisores (reverse (divisoresPropiosMaximales x)))

divisoresPropiosMaximales :: Integer -> [Integer]

divisoresPropiosMaximales x =

[ x `div` y | y <- nub (primeFactors x)]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

nOcurrenciasArbolDivisores y x = nAux y (arbolDivisores x)

nAux :: Integer -> Arbol -> Integer

nAux x (N n xs) | x == n = 1 + sum (map (nAux x) xs)

| otherwise = sum (map (nAux x) xs)

Responder

arbolDivisores :: Integer -> Arbol
arbolDivisores x =
  N x  (map arbolDivisores (divisoresPropiosMaximales x))

divisoresPropiosMaximales :: Integer -> [Integer]
divisoresPropiosMaximales x =
  [z | (z,n) <- zip xs [0..]
     , noDivisor z (drop (n+1) xs)]
  where factores x     = [y | y <- [1..x-1], mod x y == 0]
        xs             = factores x
        noDivisor x zs = and [mod y x /= 0 | y <- zs]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x y = aux x (arbolDivisores y)
  where aux n (N y xs)
          | n == y    = 1 + sum [aux n z | z <- xs]
          | otherwise = sum [aux n z | z <- xs]

arbolDivisores :: Integer -> Arbol

arbolDivisores x =

N x (map arbolDivisores (divisoresPropiosMaximales x))

divisoresPropiosMaximales :: Integer -> [Integer]

divisoresPropiosMaximales x =

[z | (z,n) <- zip xs [0..]

, noDivisor z (drop (n+1) xs)]

where factores x = [y | y <- [1..x-1], mod x y == 0]

xs = factores x

noDivisor x zs = and [mod y x /= 0 | y <- zs]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

nOcurrenciasArbolDivisores x y = aux x (arbolDivisores y)

where aux n (N y xs)

| n == y = 1 + sum [aux n z | z <- xs]

| otherwise = sum [aux n z | z <- xs]

Responder

import Data.List

arbolDivisores :: Integer -> Arbol
arbolDivisores x =
  N x [arbolDivisores y | y <- divisoresPropiosMaximales x]

divisoresPropiosMaximales :: Integer -> [Integer]
divisoresPropiosMaximales n =
  [x | x <- factores n
     , and [mod y x /= 0 | y <- (factores n \\ [x])]]

factores :: Integer -> [Integer]
factores n = [x | x <- [1..div n 2]
                , mod n x == 0]
  
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x y
  | x == 1 && y == 1 = 1
  | y == 1           = 0
  | x == y           = sum (1 : [nOcurrenciasArbolDivisores x n | n <- xs])
  | otherwise        = sum [nOcurrenciasArbolDivisores x n | n <- xs]
  where xs = divisoresPropiosMaximales y

import Data.List

arbolDivisores :: Integer -> Arbol

arbolDivisores x =

N x [arbolDivisores y | y <- divisoresPropiosMaximales x]

divisoresPropiosMaximales :: Integer -> [Integer]

divisoresPropiosMaximales n =

[x | x <- factores n

, and [mod y x /= 0 | y <- (factores n \\ [x])]]

factores :: Integer -> [Integer]

factores n = [x | x <- [1..div n 2]

, mod n x == 0]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

nOcurrenciasArbolDivisores x y

| x == 1 && y == 1 = 1

| y == 1 = 0

| x == y = sum (1 : [nOcurrenciasArbolDivisores x n | n <- xs])

| otherwise = sum [nOcurrenciasArbolDivisores x n | n <- xs]

where xs = divisoresPropiosMaximales y

Responder

import Data.List (nub, subsequences)
import Data.Numbers.Primes (primeFactors)

data Arbol = N Integer [Arbol]
  deriving (Eq, Show)
 
arbolDivisores :: Integer -> Arbol
arbolDivisores n = N n d
  where d = [arbolDivisores x | x <- divisoresPropiosMaximales n]
 
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores 1 1 = 0
nOcurrenciasArbolDivisores _ 1 = 0
nOcurrenciasArbolDivisores x y
  | x /= y =
    sum [nOcurrenciasArbolDivisores x n
        | n <- divisoresPropiosMaximales y] 
  | otherwise =
    sum (1 : [nOcurrenciasArbolDivisores x n
             | n <- divisoresPropiosMaximales y])
 
divisoresPropiosMaximales  :: Integer -> [Integer]
divisoresPropiosMaximales x = [product ys | ys <- factores x]

factores :: Integer -> [[Integer]]
factores x = 
  nub [ys | ys <- subsequences (primeFactors x) ,
            length ys == length (primeFactors x) - 1]

import Data.List (nub, subsequences)

import Data.Numbers.Primes (primeFactors)

data Arbol = N Integer [Arbol]

deriving (Eq, Show)

arbolDivisores :: Integer -> Arbol

arbolDivisores n = N n d

where d = [arbolDivisores x | x <- divisoresPropiosMaximales n]

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer

nOcurrenciasArbolDivisores 1 1 = 0

nOcurrenciasArbolDivisores _ 1 = 0

nOcurrenciasArbolDivisores x y

| x /= y =

sum [nOcurrenciasArbolDivisores x n

| n <- divisoresPropiosMaximales y]

| otherwise =

sum (1 : [nOcurrenciasArbolDivisores x n

| n <- divisoresPropiosMaximales y])

divisoresPropiosMaximales :: Integer -> [Integer]

divisoresPropiosMaximales x = [product ys | ys <- factores x]

factores :: Integer -> [[Integer]]

factores x =

nub [ys | ys <- subsequences (primeFactors x) ,

length ys == length (primeFactors x) - 1]

Responder

Árbol de divisores

Soluciones

Pensamiento

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico