Números compuestos por un conjunto de primos
Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son
|
1 |
1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,... |
El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].
Definir la función
|
1 |
compuestos :: [Integer] -> [Integer] |
tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> take 20 (compuestos [2,5,7]) [1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70] λ> take 20 (compuestos [2,5]) [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250] λ> take 20 (compuestos [2,3,5]) [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36] λ> take 20 (compuestos [3,5,7,11,13]) [1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75] λ> take 15 (compuestos [2]) [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384] λ> compuestos [2,7] !! (10^4) 57399514149595471961908157955229677377312712667508119466382354072731648 λ> compuestos [2,3,5] !! (10^5) 290237644800000000000000000000000000000 |
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
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) |