Números de Perrin
Los números de Perrin se definen por la relación de recurrencia
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.
Definir la sucesión
sucPerrin :: [Integer]
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
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
sucPerrin :: [Integer] sucPerrin = 3 : 0 : 2 : zipWith (+) sucPerrin (tail sucPerrin) 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