import Data.Numbers.Primes (primeFactors)
-- 1ª solución
-- ===========
compuestos1 :: [Integer] -> [Integer]
compuestos1 ps =
[n | n <- [1..], esCompuesto ps n]
-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen
-- a ps. Por ejemplo,
-- esCompuesto [2,3,7] 28 == True
-- esCompuesto [2,3,7] 140 == False
-- esCompuesto [2,3,5,7] 140 == True
esCompuesto :: [Integer] -> Integer -> Bool
esCompuesto ps n =
subconjunto (primeFactors n) ps
-- (subconjunto xs ys) se verifica si todos los elementos de xs
-- pertenecen a ys. Por ejemplo,
-- subconjunto [2,7,2] [7,5,2] == True
-- subconjunto [2,7,3] [7,5,2] == False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys =
all (`elem` ys) xs
-- 2ª solución
-- ===========
compuestos2 :: [Integer] -> [Integer]
compuestos2 ps =
1 : mezclaTodas (combinaciones ps)
-- (combinaciones ps) es la lista de los productos de cada elemento de
-- ps por los números compuestos con ps. Por ejemplo,
-- λ> take 8 (compuestos4 [2,5,7])
-- [1,2,4,5,7,8,10,14]
-- λ> map (take 6) (combinaciones [2,5,7])
-- [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]
combinaciones :: [Integer] -> [[Integer]]
combinaciones ps =
[[p * q | q <- compuestos2 ps] | p <- ps]
-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
-- [2,3,4,5,6,7,8,9,10,11]
-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
-- [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: [[Integer]] -> [Integer]
mezclaTodas = foldr1 xmezcla
where xmezcla (x:xs) ys = x : mezcla xs ys
-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista
-- ordenadas xs e ys. Por ejemplo,
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla [] ys = ys
mezcla xs [] = xs
mezcla us@(x:xs) vs@(y:ys) | x == y = x : mezcla xs ys
| x < y = x : mezcla xs vs
| otherwise = y : mezcla us ys
-- 3ª solución
-- ===========
compuestos3 :: [Integer] -> [Integer]
compuestos3 [] = [1]
compuestos3 (p:ps) =
mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]
-- 4ª solución
-- ===========
compuestos4 :: [Integer] -> [Integer]
compuestos4 ps = foldl aux xs (tail ps)
where p = head ps
xs = [p^k | k <- [0..]]
aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]
-- 5ª solución
-- ===========
compuestos5 :: [Integer] -> [Integer]
compuestos5 = foldl aux [1]
where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]
-- 6ª solución
-- ===========
compuestos6 :: [Integer] -> [Integer]
compuestos6 xs = aux
where aux = 1 : mezclas xs aux
mezclas [] _ = []
mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)
-- Comparación de eficiencia
-- =========================
-- λ> compuestos1 [2,3,5] !! 300
-- 84375
-- (5.85 secs, 2,961,101,088 bytes)
-- λ> compuestos2 [2,3,5] !! 300
-- 84375
-- (3.54 secs, 311,137,952 bytes)
-- λ> compuestos2 [2,3,5] !! 400
-- 312500
-- (13.01 secs, 1,229,801,184 bytes)
-- λ> compuestos3 [2,3,5] !! 400
-- 312500
-- (0.02 secs, 2,066,152 bytes)
-- λ> compuestos3 [2,3,5] !! 20000
-- 15441834907098675000000
-- (1.57 secs, 203,061,864 bytes)
-- λ> compuestos4 [2,3,5] !! 20000
-- 15441834907098675000000
-- (0.40 secs, 53,335,080 bytes)
-- λ> compuestos4 [2,3,5] !! 50000
-- 2379528690747474604574166220800
-- (1.25 secs, 170,058,496 bytes)
-- λ> compuestos5 [2,3,5] !! 50000
-- 2379528690747474604574166220800
-- (1.26 secs, 170,104,648 bytes)
-- λ> compuestos6 [2,3,5] !! 50000
-- 2379528690747474604574166220800
-- (0.26 secs, 40,490,280 bytes) |
José A. Alonso