Números de Perrin

Los números de Perrin se definen por la elación de recurrencia

   P(n) = P(n - 2) + P(n - 3) si n > 2,

1	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.

1	P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

   sucPerrin :: [Integer]

1	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

λ> 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

4 Comentarios

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)

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)

Responder

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]

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]

Responder

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.

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.

Responder

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

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

Responder

Números de Perrin

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico