Menu Close

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

import Data.List (genericIndex, unfoldr)
import Data.Numbers.Primes (isPrime)
import Test.QuickCheck
 
-- 1ª definición
sucPerrin1 :: [Integer]
sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)
 
-- 2ª definición
sucPerrin2 :: [Integer]
sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
  where op (a,b,c) = (b,c,a+b)
 
-- 3ª definición
sucPerrin3 :: [Integer]
sucPerrin3 =
  unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))
 
-- Comparación de eficiencia
--    λ> length (show (sucPerrin1 !! (10^5)))
--    12213
--    (1.44 secs, 295,373,680 bytes)
--    λ> length (show (sucPerrin2 !! (10^5)))
--    12213
--    (1.22 secs, 301,493,408 bytes)
--    λ> length (show (sucPerrin3 !! (10^5)))
--    12213
--    (0.86 secs, 296,911,304 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

9 soluciones de “Números de Perrin

  1. paumacpar
    import Data.Numbers.Primes (isPrime)
    import Test.QuickCheck
     
    sucPerrin :: [Integer]
    sucPerrin = ys
      where (zs, ts, xs,ys) = (zipWith (+) xs ys ,2:zs,0:ts,3:xs)
     
    propPerrin :: Integer -> Property
    propPerrin n =
      n > 1 ==>
      (mod (sucPerrin !! (fromInteger n)) n == 0) == isPrime n
  2. albcercid
    sucPerrin :: [Integer]
    sucPerrin = 3:0:2:zipWith (+) (tail sucPerrin) sucPerrin
     
    sucPerrint :: [Int]
    sucPerrint = 3:0:2:zipWith (+) (tail sucPerrint) sucPerrint
     
    -- Nota: he definido la función 'sucPerrint' porque me era imposible usar 'sucPerrin' en la función 'propPerrin', debido a un
    -- problema con los tipos Int e Integer.
     
    propPerrin :: Int -> Property
    propPerrin n = n > 1 ==> dobleImplicacion (isPrime n, mod (sucPerrint !! n) n == 0)
                    where  dobleImplicacion (a,b) = a==b
     
    -- λ> quickCheck propPerrin
    -- +++ OK, passed 100 tests.
    • albcercid
      import Data.Numbers.Primes (isPrime)
      import Test.QuickCheck
       
      sucPerrin :: [Integer]
      sucPerrin = 3 : 0 : 2 : zipWith (+) (tail sucPerrin) sucPerrin
       
      propPerrin n =
        n > 1 ==>
        dobleImplicacion (isPrime n,
                          mod (fromIntegral (sucPerrin !! n)) n == 0)
        where dobleImplicacion (a,b) = a == b
       
      -- λ> quickCheck propPerrin
      -- +++ OK, passed 100 tests.
  3. Fran Cruz
    import Data.Numbers.Primes (isPrime)
    import Test.QuickCheck
     
    sucPerrin :: [Integer]
    sucPerrin = 3: 0: 2: zipWith (+) xs ys
      where xs@(_:ys) = sucPerrin
     
    prop_Perrin :: (Positive Integer) -> Bool
    prop_Perrin (Positive n) = (x `mod` m == 0) == isPrime m
      where m = n + 1
            x = sucPerrin !! (fromIntegral m)
     
    {- λ> quickCheck prop_Perrin
       +++ OK, passed 100 tests.
     
       Sin embargo...
       λ> prop_Perrin (Positive 271440)
       False
       λ> let m = 271441
       λ> let x = sucPerrin !! m
       λ> x `mod` m == 0
       True
       λ> isPrime m
       False
    -}
  4. cescarde
    -- 1ª Definición:
    p1 :: Integer -> Integer
    p1 0 = 3
    p1 1 = 0
    p1 2 = 2
    p1 n = p1 (n-2) + p1 (n-3)
     
    sucPerrin1 :: [Integer]
    sucPerrin1 = [p1 n | n <- [0..]]
     
    -- 2ª Definición:
    p2 :: Integer -> Integer
    p2 n = pAux n 3 0 2
      where pAux 0 a b c = a
            pAux n a b c = pAux (n-1) b c (a+b)
     
    sucPerrin2 :: [Integer]
    sucPerrin2 = [p2 n | n <- [0..]]
  5. Chema Cortés
    import Test.QuickCheck
    import Data.Numbers.Primes (isPrime)
    import Data.List (unfoldr,genericIndex)
     
    sucPerrin :: [Integer]
    sucPerrin = sucPerrin3
     
    sucPerrin1 :: [Integer]
    sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)
     
    sucPerrin2 :: [Integer]
    sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
      where op (a,b,c) = (b,c,a+b)
     
    sucPerrin3 :: [Integer]
    sucPerrin3 = unfoldr ((a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))
     
    prop_perrin :: Positive Integer -> Property
    prop_perrin (Positive n) = n > 1 ==> esDivisible == esPrimo
      where esDivisible = (genericIndex sucPerrin n) `mod` n == 0
            esPrimo = isPrime n
  6. Juanjo Ortega (juaorture)
    sucPerrin :: [Integer]
    sucPerrin = aux 3 0 2
      where aux x y z = x : aux y z (x+y)
    • Juanjo Ortega (juaorture)
      import Test.QuickCheck
      import Data.Numbers.Primes
       
      sucPerrinA6 :: [Integer]
      sucPerrinA6 = aux 3 0 2
        where aux x y z = x : aux y z (x+y) 
       
      posicion :: Integer -> [a] -> a
      posicion 0 (x:xs) = x
      posicion n (x:xs) = posicion (n-1) xs
       
      prop_Perrin1 :: Integer -> Property
      prop_Perrin1 n =
        n > 1 && isPrime n ==> (posicion n sucPerrin) `rem` n == 0
       
      -- *Main> quickCheck prop_Perrin1
      -- +++ OK, passed 100 tests.
       
      prop_Perrin2 :: Integer -> Property
      prop_Perrin2 n =
        n > 1 && (posicion n sucPerrin) `rem` n == 0 ==> isPrime n
       
      -- *Main> quickCheck prop_Perrin2
      -- +++ OK, passed 100 tests.

      Nota: La función “posicion n xs” es parecida a la predefinida en haskell “!!” pero he tenido que definirla por los diferentes tipos de esa función y la función “rem”.

  7. luimotmar
    p :: Integer -> Integer
    p 0 = 3
    p 1 = 0
    p 2 = 2
    p n = p (n - 2) + p (n - 3)
     
    sucPerrin :: [Integer]
    sucPerrin = 3 : 0 : 2 : map p [n | n <- [3..]]

Escribe tu solución

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