Menu Close

Números de Perrin

José A. Alonso,

Los números de Perrin se definen por la elació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

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
Inicial
, , , , , , , , , ,

4 soluciones de “Números de Perrin”

  1. Responder
    margomnot 
    import Data.Array
 
sucPerrin :: [Integer]
sucPerrin = [(vectorSucPerrin n) ! n | n <- [0..]]
 
vectorSucPerrin :: Integer -> Array Integer Integer
vectorSucPerrin 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)
  2. Responder
    Enrique Zubiría 
    import Test.QuickCheck
import Data.Numbers.Primes
 
sucPerrin :: [Integer]
sucPerrin = 3 : 0 : 2 : zipWith (+) sucPerrin (tail sucPerrin)
 
prop_numPerrin1 :: Integer -> Property
prop_numPerrin1 n =
  n > 1 && isPrime n ==> rem (sucPerrin!!(fromIntegral $ abs n)) n == 0
 
prop_numPerrin2 :: Integer -> Property
prop_numPerrin2 n =
  n > 1 && rem (sucPerrin!!(fromIntegral $ abs n)) n == 0 ==> isPrime n
 
prop_numPerrin :: Integer -> Property
prop_numPerrin n = conjoin [prop_numPerrin1 n, prop_numPerrin2 n]
  3. Responder
    rebgongor 
    import Data.Numbers.Primes
import Test.QuickCheck
 
sucPerrin :: [Integer]
sucPerrin = map numeroPerrin [0..]
  where numeroPerrin 0 = 3
        numeroPerrin 1 = 0
        numeroPerrin 2 = 2
        numeroPerrin n = numeroPerrin (n-2) + numeroPerrin (n-3)
 
propiedad :: Integer -> Property
propiedad n = p ==> q && q ==> p
  where p = n > 1 && isPrime n
        q = n > 1 && rem (sucPerrin!!(fromIntegral n)) n == 0
 
-- λ> quickCheckWith (stdArgs {maxSize=60}) propiedad
-- +++ OK, passed 100 tests; 598 discarded.
  4. Responder
    juasuator1 
    import Data.Numbers.Primes
import Test.QuickCheck
 
sucPerrin :: [Integer]
sucPerrin = aux 3 0 2
  where aux a b c = a : aux b c (a+b)
 
propiedad :: Integer -> Property
propiedad n = p ==> q  &&  q  ==> p
  where p =  n > 1 && isPrime n
        q =  n > 1 && mod (sucPerrin !! (fromIntegral n )) n == 0

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.