Los números de Perrin se definen por la elación de recurrencia
P(n) = P(n - 2) + P(n - 3) si n > 2, |
P(n) = P(n - 2) + P(n - 3) si n > 2,
con los valores iniciales
P(0) = 3, P(1) = 0 y P(2) = 2. |
P(0) = 3, P(1) = 0 y P(2) = 2.
Definir la sucesión
cuyos elementos son los números de Perrin. Por ejemplo,
λ> take 15 sucPerrin
[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
λ> length (show (sucPerrin !! (2*10^5)))
24425 |
λ> take 15 sucPerrin
[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
λ> length (show (sucPerrin !! (2*10^5)))
24425
Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.
Soluciones
import Data.List (genericIndex, unfoldr)
import Data.Numbers.Primes (isPrime)
import Test.QuickCheck
-- 1ª solución
sucPerrin1 :: [Integer]
sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)
-- 2ª solución
sucPerrin2 :: [Integer]
sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
where op (a,b,c) = (b,c,a+b)
-- 3ª solución
sucPerrin3 :: [Integer]
sucPerrin3 =
unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))
-- 4ª solución
sucPerrin4 :: [Integer]
sucPerrin4 = [vectorPerrin n ! n | n <- [0..]]
vectorPerrin :: Integer -> Array Integer Integer
vectorPerrin n = v where
v = array (0,n) [(i,f i) | i <- [0..n]]
f 0 = 3
f 1 = 0
f 2 = 2
f i = v ! (i-2) + v ! (i-3)
-- Comparación de eficiencia
-- λ> length (show (sucPerrin1 !! (3*10^5)))
-- 36638
-- (1.62 secs, 2,366,238,984 bytes)
-- λ> length (show (sucPerrin2 !! (3*10^5)))
-- 36638
-- (1.40 secs, 2,428,701,384 bytes)
-- λ> length (show (sucPerrin3 !! (3*10^5)))
-- 36638
-- (1.14 secs, 2,409,504,864 bytes)
-- λ> length (show (sucPerrin4 !! (3*10^5)))
-- 36638
-- (1.78 secs, 2,585,400,776 bytes)
-- Usaremos la 3ª
sucPerrin :: [Integer]
sucPerrin = sucPerrin3
-- La propiedad es
conjeturaPerrin :: Integer -> Property
conjeturaPerrin n =
n > 1 ==>
(perrin n `mod` n == 0) == isPrime n
-- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por
-- ejemplo,
-- perrin 4 == 2
-- perrin 5 == 5
-- perrin 6 == 5
perrin :: Integer -> Integer
perrin n = sucPerrin `genericIndex` n
-- La comprobación es
-- λ> quickCheck conjeturaPerrin
-- +++ OK, passed 100 tests.
-- Nota: Aunque QuickCheck no haya encontrado contraejemplos, la
-- propiedad no es cierta. Sólo lo es una de las implicaciones: si n es
-- primo, entonces el n-ésimo término de la sucesión de Perrin es
-- divisible por n. La otra es falsa y los primeros contraejemplos son
-- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291 |
import Data.List (genericIndex, unfoldr)
import Data.Numbers.Primes (isPrime)
import Test.QuickCheck
-- 1ª solución
sucPerrin1 :: [Integer]
sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)
-- 2ª solución
sucPerrin2 :: [Integer]
sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
where op (a,b,c) = (b,c,a+b)
-- 3ª solución
sucPerrin3 :: [Integer]
sucPerrin3 =
unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))
-- 4ª solución
sucPerrin4 :: [Integer]
sucPerrin4 = [vectorPerrin n ! n | n <- [0..]]
vectorPerrin :: Integer -> Array Integer Integer
vectorPerrin n = v where
v = array (0,n) [(i,f i) | i <- [0..n]]
f 0 = 3
f 1 = 0
f 2 = 2
f i = v ! (i-2) + v ! (i-3)
-- Comparación de eficiencia
-- λ> length (show (sucPerrin1 !! (3*10^5)))
-- 36638
-- (1.62 secs, 2,366,238,984 bytes)
-- λ> length (show (sucPerrin2 !! (3*10^5)))
-- 36638
-- (1.40 secs, 2,428,701,384 bytes)
-- λ> length (show (sucPerrin3 !! (3*10^5)))
-- 36638
-- (1.14 secs, 2,409,504,864 bytes)
-- λ> length (show (sucPerrin4 !! (3*10^5)))
-- 36638
-- (1.78 secs, 2,585,400,776 bytes)
-- Usaremos la 3ª
sucPerrin :: [Integer]
sucPerrin = sucPerrin3
-- La propiedad es
conjeturaPerrin :: Integer -> Property
conjeturaPerrin n =
n > 1 ==>
(perrin n `mod` n == 0) == isPrime n
-- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por
-- ejemplo,
-- perrin 4 == 2
-- perrin 5 == 5
-- perrin 6 == 5
perrin :: Integer -> Integer
perrin n = sucPerrin `genericIndex` n
-- La comprobación es
-- λ> quickCheck conjeturaPerrin
-- +++ OK, passed 100 tests.
-- Nota: Aunque QuickCheck no haya encontrado contraejemplos, la
-- propiedad no es cierta. Sólo lo es una de las implicaciones: si n es
-- primo, entonces el n-ésimo término de la sucesión de Perrin es
-- divisible por n. La otra es falsa y los primeros contraejemplos son
-- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291