Cadenas de divisores
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 |
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 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] |
Referencias
- Sucesión A163272 de OEIS.
- Ordered and unordered factorizations of integers por A. Knopfmacher y M. Mays
Puede hacerse tan eficiente como la generación de todos los divisores si al generar los divisores se almacena la relación generadora a partir de la descomposición en factores. Aquí no se almacena dicha relación y se revisa divisibilidad. Aun así, tiene la misma complejidad («sólo» ahorraríamos la división en cada caso).
No, no tiene la misma complejidad, siguiendo la relación de generación saltaríamos la revisión de divisibilidad para toda una secuencia de potenciales divisores (ej. si es n=p q^b con p>q^b ahorraríamos revisar los q, q^2, q^3, … cuando el previo es p). Es decir, aún puede hacerse notablemente más eficiente.
Usando la relación de divisibilidad es notablemente más rápido, no obstante, no encuentro una forma de mantener dicha relación y generar las subsecuencias una única vez (sin repetidos), pero creo podría hacerse y evitar el
nubOrd
(con lo que sería todavía más rápido).