Números de Perrin

PorJosé A. Alonso 29-diciembre-201625-abril-2021

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

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

1	271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

9 Comentarios

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

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

Responder

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.

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.

Responder

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.

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.

Responder

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

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

Responder

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

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

Responder

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

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

Responder

sucPerrin :: [Integer]
sucPerrin = aux 3 0 2
  where aux x y z = x : aux y z (x+y)

sucPerrin :: [Integer]

sucPerrin = aux 3 0 2

where aux x y z = x : aux y z (x+y)

Responder

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.

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

Responder

luimotmar dice:

30-diciembre-2016 a las 18:26

Haskell

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

1
2
3
4
5
6
7
8

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

Responder

Números de Perrin

Soluciones

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

9 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico