Primos equidistantes
Definir la función
|
1 |
primosEquidistantes :: Integer -> [(Integer,Integer)] |
tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,
|
1 2 3 4 5 |
take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)] take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)] take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)] take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)] primosEquidistantes 4 !! (10^5) == (18467047,18467051) |
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 |
import Data.Numbers.Primes (primes) -- 1ª solución -- =========== primosEquidistantes1 :: Integer -> [(Integer,Integer)] primosEquidistantes1 k = aux primos where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) -- (primo x) se verifica si x es primo. Por ejemplo, -- primo 7 == True -- primo 8 == False primo :: Integer -> Bool primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x] -- primos es la lista de los números primos. Por ejemplo, -- take 10 primos == [2,3,5,7,11,13,17,19,23,29] primos :: [Integer] primos = 2 : [x | x <- [3,5..], primo x] -- 2ª solución -- =========== primosEquidistantes2 :: Integer -> [(Integer,Integer)] primosEquidistantes2 k = aux primos2 where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) primos2 :: [Integer] primos2 = criba [2..] where criba (p:ps) = p : criba [n | n <- ps, mod n p /= 0] -- 3ª solución -- =========== primosEquidistantes3 :: Integer -> [(Integer,Integer)] primosEquidistantes3 k = [(x,y) | (x,y) <- zip primos2 (tail primos2) , y - x == k] -- 4ª solución -- =========== primosEquidistantes4 :: Integer -> [(Integer,Integer)] primosEquidistantes4 k = aux primes where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) -- 5ª solución -- =========== primosEquidistantes5 :: Integer -> [(Integer,Integer)] primosEquidistantes5 k = [(x,y) | (x,y) <- zip primes (tail primes) , y - x == k] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_primosEquidistantes :: Int -> Integer -> Bool prop_primosEquidistantes n k = all (== take n (primosEquidistantes1 k)) [take n (f k) | f <- [primosEquidistantes2, primosEquidistantes3, primosEquidistantes4, primosEquidistantes5]] -- La comprobación es -- λ> prop_primosEquidistantes 100 4 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> primosEquidistantes1 4 !! 200 -- (9829,9833) -- (2.60 secs, 1,126,458,272 bytes) -- λ> primosEquidistantes2 4 !! 200 -- (9829,9833) -- (0.44 secs, 249,622,048 bytes) -- λ> primosEquidistantes3 4 !! 200 -- (9829,9833) -- (0.36 secs, 207,549,592 bytes) -- λ> primosEquidistantes4 4 !! 200 -- (9829,9833) -- (0.02 secs, 4,012,848 bytes) -- λ> primosEquidistantes5 4 !! 200 -- (9829,9833) -- (0.01 secs, 7,085,072 bytes) -- -- λ> primosEquidistantes2 4 !! 600 -- (41617,41621) -- (5.67 secs, 3,340,313,480 bytes) -- λ> primosEquidistantes3 4 !! 600 -- (41617,41621) -- (5.43 secs, 3,090,994,096 bytes) -- λ> primosEquidistantes4 4 !! 600 -- (41617,41621) -- (0.03 secs, 15,465,824 bytes) -- λ> primosEquidistantes5 4 !! 600 -- (41617,41621) -- (0.04 secs, 28,858,232 bytes) -- -- λ> primosEquidistantes4 4 !! (10^5) -- (18467047,18467051) -- (3.99 secs, 9,565,715,488 bytes) -- λ> primosEquidistantes5 4 !! (10^5) -- (18467047,18467051) -- (7.95 secs, 18,712,469,144 bytes) |
El código se encuentra en GitHub.