Primos o cuadrados de primos
Definir la constante
1 |
primosOcuadradosDePrimos :: [Integer] |
cuyos elementos son los número primos o cuadrados de primos. Por ejemplo,
1 2 3 4 |
λ> take 20 primosOcuadradosDePrimos [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53] λ> primosOcuadradosDePrimos !! (10^6) 15476729 |
Comprobar con QuickCheck que las lista primosOcuadradosDePrimos y unifactorizables (definida en el ejercicio anterior) son iguales.
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 |
import Test.QuickCheck import Data.Numbers.Primes (primeFactors, primes) -- 1ª solución -- =========== primosOcuadradosDePrimos :: [Integer] primosOcuadradosDePrimos = filter esPrimoOcuadradoDePrimo [2..] esPrimoOcuadradoDePrimo :: Integer -> Bool esPrimoOcuadradoDePrimo n = aux xs where xs = primeFactors n aux [_] = True aux [x,y] = x == y aux _ = False -- 2ª solución -- =========== primosOcuadradosDePrimos2 :: [Integer] primosOcuadradosDePrimos2 = mezcla primes (map (^2) primes) mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | otherwise = y : mezcla (x:xs) ys -- Comparación de eficiencia -- ========================= -- λ> primosOcuadradosDePrimos !! (2*10^4) -- 223589 -- (3.08 secs, 9,829,725,096 bytes) -- λ> primosOcuadradosDePrimos2 !! (2*10^4) -- 223589 -- (0.04 secs, 73,751,888 bytes) -- -- λ> primosOcuadradosDePrimos2 !! (5*10^5) -- 7362497 -- (1.29 secs, 3,192,803,040 bytes) -- Propiedad de equivalencia -- ========================= -- La propiedad es prop_equivalencia :: Int -> Property prop_equivalencia n = n >= 0 ==> primosOcuadradosDePrimos2 !! n == unifactorizables !! n -- unifactorizables es la lísta de los números enteros mayores que 1 -- que se pueden escribir sólo de una forma única como producto de -- enteros distintos mayores que uno. Por ejemplo, -- λ> take 20 unifactorizables -- [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53] -- λ> unifactorizables !! 300 -- 1873 unifactorizables :: [Integer] unifactorizables = [n | n <- [2..] , length (sublistasConProducto n [2..n]) == 1] -- (sublistasConProducto n xs) es la lista de las sublistas de la -- lista ordenada estrictamente creciente xs (cuyos elementos son -- enteros mayores que 1) cuyo producto es el número entero n (con n -- mayor que 1). Por ejemplo, -- λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16] -- [[2,4,9],[3,4,6]] -- λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16] -- [[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]] -- λ> sublistasConProducto 2 [4,7] -- [] sublistasConProducto :: Integer -> [Integer] -> [[Integer]] sublistasConProducto _ [] = [] sublistasConProducto n (x:xs) | x > n = [] | x == n = [[x]] | r == 0 = map (x:) (sublistasConProducto q xs) ++ sublistasConProducto n xs | otherwise = sublistasConProducto n xs where (q,r) = quotRem n x -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. |
Pensamiento
Despacito y buena letra: el hacer las cosas bien importa más que el hacerlas.
Antonio Machado
No genera la lista infinita, sólo los primeros elementos.
Puesto que Rebeca ha solucionado ya el ejercicio, igualmente propongo otra solución alternativa modificando el tipo de la función, simplemente por experimentar. Sería con una función de un entero en una lista de enteros.
Tampoco genera la lista infinita.