Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].
Definir la función
|
1 |
cadenasDivisores :: Int -> [[Int]] |
tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,
|
1 2 3 4 5 6 |
λ> cadenasDivisores 12 [[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]] λ> length (cadenaDivisores 48) 48 λ> length (cadenaDivisores 120) 132 |
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import Data.List (sort) import Data.Numbers.Primes (isPrime) -- 1ª definición -- ============= cadenasDivisores :: Int -> [[Int]] cadenasDivisores n = sort (extiendeLista [[n]]) where extiendeLista [] = [] extiendeLista ((1:xs):yss) = xs : extiendeLista yss extiendeLista ((x:xs):yss) = extiendeLista ([y:x:xs | y <- divisores x] ++ yss) -- (divisores x) es la lista decreciente de los divisores de x distintos -- de x. Por ejemplo, -- divisores 12 == [6,4,3,2,1] divisores :: Int -> [Int] divisores x = [y | y <- [a,a-1..1], x `mod` y == 0] where a = x `div` 2 -- 2ª definición -- ============= cadenasDivisores2 :: Int -> [[Int]] cadenasDivisores2 = sort . aux where aux 1 = [[]] aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)] -- 3ª definición -- ============= cadenasDivisores3 :: Int -> [[Int]] cadenasDivisores3 = sort . map reverse . aux where aux 1 = [[]] aux n = map (n:) (concatMap aux (divisores3 n)) -- (divisores3 x) es la lista creciente de los divisores de x distintos -- de x. Por ejemplo, -- divisores3 12 == [1,2,3,4,6] divisores3 :: Int -> [Int] divisores3 x = [y | y <- [1..a], x `mod` y == 0] where a = x `div` 2 -- 1ª definición de nCadenasDivisores -- ================================== nCadenasDivisores1 :: Int -> Int nCadenasDivisores1 = length . cadenasDivisores -- 2ª definición de nCadenasDivisores -- ================================== nCadenasDivisores2 :: Int -> Int nCadenasDivisores2 1 = 1 nCadenasDivisores2 n = sum [nCadenasDivisores2 x | x <- divisores n] |