Acotación del primorial
El primorial de un número natural n es el producto de todos los números primos menores o iguales a n. Por ejemplo, el primorial de 5 es 30 porque el producto de los primos menores o iguales que 5 es
|
1 |
2 * 3 * 5 = 30 |
La propiedad de Erdös de acotación de los primoriales afirma que
Para todo número natural n, su primorial es menor o igual que 4ⁿ.
Definir las funciones
|
1 2 |
primorial :: Integer -> Integer primoriales :: [Integer] |
tales que
- (primorial n) es el primorial de n. Por ejemplo,
|
1 2 3 |
primorial 3 == 6 primorial 5 == 30 primorial 8 == 210 |
- primoriales es la sucesión de los primoriales. Por ejemplo,
|
1 2 |
λ> take 15 primoriales [1,1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030] |
Comprobar con QuickCheck la propiedad de Erdös de acotación de los primoriales.
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 Data.Numbers.Primes import Test.QuickCheck -- 1ª definición de primorial -- ========================== primorial :: Integer -> Integer primorial n = product (takeWhile (<= n) primes) -- 2ª definición de primorial -- ========================== primorial2 :: Integer -> Integer primorial2 0 = 1 primorial2 n | gcd n x == 1 = n*x | otherwise = x where x = primorial2 (n-1) -- Comparación de eficiencia -- ========================= -- λ> length (show (primorial (5*10^5))) -- 216852 -- (1.65 secs, 2,472,977,584 bytes) -- λ> length (show (primorial2 (5*10^5))) -- 216852 -- (3.56 secs, 2,719,162,272 bytes) -- 1ª definición de primoriales -- ============================ -- λ> take 15 primoriales -- [1,1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030] primoriales :: [Integer] primoriales = map primorial [0..] -- 2ª definición de primoriales -- ============================ -- λ> take 15 primoriales2 -- [1,1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030] primoriales2 :: [Integer] primoriales2 = map primorial2 [0..] -- 3ª definición de primoriales -- ============================ -- λ> take 15 primoriales3 -- [1,1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030] primoriales3 :: [Integer] primoriales3 = scanl1 f [1..] where f x n | gcd n x == 1 = n*x | otherwise = x -- Comparación de eficiencia -- ========================= -- λ> minimum (take 5000 primoriales) -- 1 -- (1.56 secs, 4,857,760,464 bytes) -- λ> minimum (take 5000 primoriales2) -- 1 -- (9.39 secs, 10,942,848,240 bytes) -- λ> minimum (take 5000 primoriales3) -- 1 -- (0.01 secs, 5,575,024 bytes) -- -- λ> minimum (take 6000 primoriales) -- 1 -- (2.22 secs, 7,013,937,248 bytes) -- λ> minimum (take 6000 primoriales3) -- 1 -- (0.01 secs, 6,737,328 bytes) -- Propiedad -- ========= prop_primorial :: Integer -> Property prop_primorial n = n >= 0 ==> primorial n <= 4^n -- La comprobación es -- λ> quickCheck prop_primorial -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
«Las matemáticas son la reina de las ciencias y la teoría de los números es la reina de las matemáticas.»
Una variante de la definición de primorial sería la siguiente: