La sucesión de Perrin en Haskell

Esta relación de ejercicios está dedicada al estudio de propiedades de la sucesión de Perrin Dicha sucesión está definida por la relación de recurrencia

P(0) = 3,
P(1) = 0,
P(2) = 2,
P(n) = P(n-2) + P(n-3), para n > 2

La serie comienza por

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, …

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función 
--    perrin :: Integer -> Integer
-- tal que (perrin n) es el n-ésimo término de la sucesión de
-- Perrin. Por ejemplo,  
--    perrin 8                  ==  10
--    [perrin x | x <- [0..9]]  == [3,0,2,3,2,5,5,7,10]
-- ---------------------------------------------------------------------

perrin :: Integer -> Integer
perrin 0 = 3
perrin 1 = 0
perrin 2 = 2
perrin n = perrin (n-2) + perrin (n-3)

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función 
--    perrinIter :: Integer -> Integer
-- tal que (perrinIter n) es n-ésimo término de la sucesión de Perrin
-- calculada de manera iterativa usando acumuladores. Por ejemplo, para 
-- calcular el término octavo,
--    n | a | b | c 
--   ---+---+---+----
--    8 | 3 | 0 | 2 
--    7 | 0 | 2 | 3 
--    6 | 2 | 3 | 2 
--    5 | 3 | 2 | 5 
--    4 | 2 | 5 | 5 
--    3 | 5 | 5 | 7 
--    2 | 5 | 7 | 10
--    1 | 7 |10 | 10
--    0 |10 |10 | 17
-- ---------------------------------------------------------------------

perrinIter :: Integer -> Integer
perrinIter n = perrinIterAux n 3 0 2

perrinIterAux :: Integer -> Integer -> Integer -> Integer -> Integer
perrinIterAux 0     a b c = a
perrinIterAux (n+1) a b c = perrinIterAux n b c (a+b)


-- ---------------------------------------------------------------------
-- Ejercicio 3. Escribir el proceso de cálculo de perrinIter 
-- ---------------------------------------------------------------------

-- El procesos es
--    perrinIter 8 =
--    = perrinIterAux 8  3  0  2 
--    = perrinIterAux 7  0  2  3 
--    = perrinIterAux 6  2  3  2 
--    = perrinIterAux 5  3  2  5 
--    = perrinIterAux 4  2  5  5 
--    = perrinIterAux 3  5  5  7 
--    = perrinIterAux 2  5  7 10 
--    = perrinIterAux 1  7 10 10 
--    = perrinIterAux 0 10 10 17 
--    = 10

-- ---------------------------------------------------------------------
-- Ejercicio 4. Establecer la relación existente entre perrinIter y
-- perrinIterAux y comprobarla con QuickCheck. 
-- ---------------------------------------------------------------------

-- La propiedad es
prop_perrinIterAux i j =
    i >= 0 && j >= 0 ==>
      pIA i (pI j) (pI (j+1)) (pI (j+2)) == pI (j+i)
      where pI  = perrinIter
            pIA = perrinIterAux

-- La comprobación es
--    ghci> quickCheck prop_perrinIterAux
--    OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 5. Comprobar que las definiciones perrin y perrinIter
-- coinciden sobre los 20 primeros términos de la sucesión.
-- ---------------------------------------------------------------------

-- La comprobación es
--    ghci> and [perrin x == perrinIter x | x <- [0..19]]
--    True

-- ---------------------------------------------------------------------
-- Ejercicio 6. Comparar los costes de calcular (perrin 50) y 
-- (perrinIter 50).
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> :set +s
--    ghci> perrin 50
--    1276942
--    (5.80 secs, 203889276 bytes)
--    ghci> perrinIter 50
--    1276942
--    (0.00 secs, 0 bytes)
--    ghci> :unset +s

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función 
--    cocientePerrin :: Integer -> Double
-- tal que (cocientePerrin n) es el cociente entre el término n-ésimo de
-- la sucesión de Perrin y su término anterior, para n >= 3. Por ejemplo,
--    cocientePerrin 5  ==  2.5
--    cocientePerrin 6  ==  1.0
-- ---------------------------------------------------------------------

cocientePerrin :: Integer -> Double
cocientePerrin n  
    | n >= 3 = (perrin' n)/(perrin' (n-1))
    where perrin' n = fromIntegral (perrinIter n)

-- ---------------------------------------------------------------------
-- Ejercicio 8, Calcular el cociente de Perrin para n de 3 a 50.
-- ---------------------------------------------------------------------

-- El cálculo es
--    ghci> [cocientePerrin n | n <- [3..50]]
--    [1.5,               0.6666666666666666, 2.5, 
--    1.0,                1.4,                1.4285714285714286, 
--    1.2,                1.4166666666666667, 1.2941176470588236, 
--    1.3181818181818181, 1.3448275862068966, 1.3076923076923077, 
--    1.3333333333333333, 1.3235294117647058, 1.3222222222222222, 
--    1.3277310924369747, 1.3227848101265822, 1.325358851674641, 
--    1.3249097472924187, 1.32425068119891,   1.3251028806584362, 
--    1.3245341614906831, 1.3247362250879249, 1.3247787610619468, 
--    1.3246492985971945, 1.32476046394352,   1.3247049866768177,
--    1.3247126436781609, 1.3247288503253796, 1.324709349926314, 
--    1.3247218788627935, 1.3247177381729962, 1.3247164893991688, 
--    1.3247195193279098, 1.3247170265714057, 1.3247182159738213, 
--    1.3247180988540976, 1.3247177043406195, 1.3247181492342783, 
--    1.324717874044412,  1.3247179578589308, 1.324717992419995, 
--    1.3247179218053005, 1.3247179775532176, 1.3247179521808965,
--    1.3247179535727094, 1.3247179630950467, 1.3247179529740076]

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función 
--    proximos :: (Num a, Ord a) => [a] -> a -> [a]
-- tal que (proximos xs d) es el primer par de elementos consecutivos de
-- la lista xs tal que el valor absoluto de su diferencia es menor o
-- igual que d. Por ejemplo,
--    proximos :: (Num a, Ord a) => [a] -> a -> [a]
--    proximos [3,5,6,9,10] 1  ==  [5,6]
--    proximos [3,5,4,9,10] 1  ==  [5,4]
--    proximos [3,5,3,9,12] 1  ==  []
-- ---------------------------------------------------------------------

proximos [] _  = []
proximos [x] _ = []
proximos (x:y:xs) d 
    | abs(x-y) <= d = [x,y]
    | otherwise     = proximos (y:xs) d

-- ---------------------------------------------------------------------
-- Ejercicio 10. Calcular los dos primeros términos consecutivos de la
-- sucesión de cocientes de Perrin tales que el valor absoluto de su
-- diferencia sea menor que 10^(-32). ¿Qué se puede decir del límite
-- de la sucesión de cocientes? 
-- ---------------------------------------------------------------------

-- El cálculo es
--    ghci> proximos [cocientePerrin n | n <- [3..]] 1e-32
--    [1.324717957244746,1.324717957244746]
-- Esto indica que el límite de la sucesión de cocientes es
-- 1.324717957244746. 

-- ---------------------------------------------------------------------
-- Ejercicio 11. Sea p(n) el n-ésimo término de la sucesión de Perrin y
-- q(n)=p(n)/p(n-1) (para n >= 3). Demostrar que el límite de q(n) es
-- una raíz de la ecuación x^3-x-1=0.
-- ---------------------------------------------------------------------

-- Por definición de la sucesión de Perrin, se tiene que
--    P(n) = P(n-2)+P(n-3).
-- Por tanto,
--    P(n)/P(n-1)} 
--    = P(n-2)/P(n-1)} + P(n-3)/P(n-2) * P(n-2)/P(n-1)
--    = P(n-2)/P(n-1)} + 1/(P(n-3)/P(n-2)) * 1/(P(n-2)/P(n-1))
-- Sea x el límite de Q(n). Entonces
--    x = 1/x + 1/x^2
-- Por tanto,
--    x^3 = x+1
-- y x es una raíz de x^3-x-1 = 0.

-- ---------------------------------------------------------------------
-- Ejercicio 12. Las raíces de una ecuación pueden aproximarse por el
-- método de bisección que se basa en el siguiente teorema: 
--    [Teorema del valor medio] Sea f una función continua en un
--    intervalo [a,b] y supongamos que f(a) y f(b) tienen signos
--    opuestos. Entonces para cada y entre f(a) y f(b), existe un x en
--    [a,b] tal que f(x)=y. 
-- El método de bisección consiste en calcular el punto medio del
-- intervalo: m=(a+b)/2. Se consideran tres casos:
-- * si |f(m)| < 10^{-9}, entonces m es una raíz de f(x)=0,
-- * si f(m) tiene el mismo signo que f(a) se repite el procedimiento en 
--   el intervalo [m,b],
-- * en otro caso, se repite el procedimiento en el intervalo [a,m].
-- 
-- Definir la función 
--    biseccion :: (Double -> Double) -> Double -> Double -> Double
-- tal que (biseccion f a b) es la raíz de f en el intervalo [a,b]
-- calculada por el método de bisección. Por ejemplo, 
--    biseccion (\x -> x^2-9) 2 5  ==>  3.0000000001164153
-- ---------------------------------------------------------------------

biseccion :: (Double -> Double) -> Double -> Double -> Double
biseccion f a b 
    | abs (f m) < 1e-9             = m
    | signum (f m) == signum (f a) = biseccion f m b
    | otherwise                    = biseccion f a m 
    where m = (a+b)/2

-- ---------------------------------------------------------------------
-- Ejercicio 13. Calcular por el método de bisección la solución de
-- x^3-x-1=0 en el intervalo [1,2] y compararla con el límite de la
-- sucesión de cocientes de Perrin. 
-- ---------------------------------------------------------------------

-- La solución se calcula por
--    ghci> biseccion (\x -> x^3-x-1) 1 2
--    1.324717957060784
-- Se observa que coincide con el límite de la sucesión de cocientes de Perrin.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir la función

-- perrin :: Integer -> Integer

-- tal que (perrin n) es el n-ésimo término de la sucesión de

-- Perrin. Por ejemplo,

-- perrin 8 == 10

-- [perrin x | x <- [0..9]] == [3,0,2,3,2,5,5,7,10]

-- ---------------------------------------------------------------------

perrin :: Integer -> Integer

perrin 0 = 3

perrin 1 = 0

perrin 2 = 2

perrin n = perrin (n-2) + perrin (n-3)

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- perrinIter :: Integer -> Integer

-- tal que (perrinIter n) es n-ésimo término de la sucesión de Perrin

-- calculada de manera iterativa usando acumuladores. Por ejemplo, para

-- calcular el término octavo,

-- n | a | b | c

-- ---+---+---+----

-- 8 | 3 | 0 | 2

-- 7 | 0 | 2 | 3

-- 6 | 2 | 3 | 2

-- 5 | 3 | 2 | 5

-- 4 | 2 | 5 | 5

-- 3 | 5 | 5 | 7

-- 2 | 5 | 7 | 10

-- 1 | 7 |10 | 10

-- 0 |10 |10 | 17

-- ---------------------------------------------------------------------

perrinIter :: Integer -> Integer

perrinIter n = perrinIterAux n 3 0 2

perrinIterAux :: Integer -> Integer -> Integer -> Integer -> Integer

perrinIterAux 0 a b c = a

perrinIterAux (n+1) a b c = perrinIterAux n b c (a+b)

-- ---------------------------------------------------------------------

-- Ejercicio 3. Escribir el proceso de cálculo de perrinIter

-- ---------------------------------------------------------------------

-- El procesos es

-- perrinIter 8 =

-- = perrinIterAux 8 3 0 2

-- = perrinIterAux 7 0 2 3

-- = perrinIterAux 6 2 3 2

-- = perrinIterAux 5 3 2 5

-- = perrinIterAux 4 2 5 5

-- = perrinIterAux 3 5 5 7

-- = perrinIterAux 2 5 7 10

-- = perrinIterAux 1 7 10 10

-- = perrinIterAux 0 10 10 17

-- = 10

-- ---------------------------------------------------------------------

-- Ejercicio 4. Establecer la relación existente entre perrinIter y

-- perrinIterAux y comprobarla con QuickCheck.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_perrinIterAux i j =

i >= 0 && j >= 0 ==>

pIA i (pI j) (pI (j+1)) (pI (j+2)) == pI (j+i)

where pI = perrinIter

pIA = perrinIterAux

-- La comprobación es

-- ghci> quickCheck prop_perrinIterAux

-- OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 5. Comprobar que las definiciones perrin y perrinIter

-- coinciden sobre los 20 primeros términos de la sucesión.

-- ---------------------------------------------------------------------

-- La comprobación es

-- ghci> and [perrin x == perrinIter x | x <- [0..19]]

-- True

-- ---------------------------------------------------------------------

-- Ejercicio 6. Comparar los costes de calcular (perrin 50) y

-- (perrinIter 50).

-- ---------------------------------------------------------------------

-- La comparación es

-- ghci> :set +s

-- ghci> perrin 50

-- 1276942

-- (5.80 secs, 203889276 bytes)

-- ghci> perrinIter 50

-- 1276942

-- (0.00 secs, 0 bytes)

-- ghci> :unset +s

-- ---------------------------------------------------------------------

-- Ejercicio 7. Definir la función

-- cocientePerrin :: Integer -> Double

-- tal que (cocientePerrin n) es el cociente entre el término n-ésimo de

-- la sucesión de Perrin y su término anterior, para n >= 3. Por ejemplo,

-- cocientePerrin 5 == 2.5

-- cocientePerrin 6 == 1.0

-- ---------------------------------------------------------------------

cocientePerrin :: Integer -> Double

cocientePerrin n

| n >= 3 = (perrin' n)/(perrin' (n-1))

where perrin' n = fromIntegral (perrinIter n)

-- ---------------------------------------------------------------------

-- Ejercicio 8, Calcular el cociente de Perrin para n de 3 a 50.

-- ---------------------------------------------------------------------

-- El cálculo es

-- ghci> [cocientePerrin n | n <- [3..50]]

-- [1.5, 0.6666666666666666, 2.5,

-- 1.0, 1.4, 1.4285714285714286,

-- 1.2, 1.4166666666666667, 1.2941176470588236,

-- 1.3181818181818181, 1.3448275862068966, 1.3076923076923077,

-- 1.3333333333333333, 1.3235294117647058, 1.3222222222222222,

-- 1.3277310924369747, 1.3227848101265822, 1.325358851674641,

-- 1.3249097472924187, 1.32425068119891, 1.3251028806584362,

-- 1.3245341614906831, 1.3247362250879249, 1.3247787610619468,

-- 1.3246492985971945, 1.32476046394352, 1.3247049866768177,

-- 1.3247126436781609, 1.3247288503253796, 1.324709349926314,

-- 1.3247218788627935, 1.3247177381729962, 1.3247164893991688,

-- 1.3247195193279098, 1.3247170265714057, 1.3247182159738213,

-- 1.3247180988540976, 1.3247177043406195, 1.3247181492342783,

-- 1.324717874044412, 1.3247179578589308, 1.324717992419995,

-- 1.3247179218053005, 1.3247179775532176, 1.3247179521808965,

-- 1.3247179535727094, 1.3247179630950467, 1.3247179529740076]

-- ---------------------------------------------------------------------

-- Ejercicio 9. Definir la función

-- proximos :: (Num a, Ord a) => [a] -> a -> [a]

-- tal que (proximos xs d) es el primer par de elementos consecutivos de

-- la lista xs tal que el valor absoluto de su diferencia es menor o

-- igual que d. Por ejemplo,

-- proximos :: (Num a, Ord a) => [a] -> a -> [a]

-- proximos [3,5,6,9,10] 1 == [5,6]

-- proximos [3,5,4,9,10] 1 == [5,4]

-- proximos [3,5,3,9,12] 1 == []

-- ---------------------------------------------------------------------

proximos [] _ = []

proximos [x] _ = []

proximos (x:y:xs) d

| abs(x-y) <= d = [x,y]

| otherwise = proximos (y:xs) d

-- ---------------------------------------------------------------------

-- Ejercicio 10. Calcular los dos primeros términos consecutivos de la

-- sucesión de cocientes de Perrin tales que el valor absoluto de su

-- diferencia sea menor que 10^(-32). ¿Qué se puede decir del límite

-- de la sucesión de cocientes?

-- ---------------------------------------------------------------------

-- El cálculo es

-- ghci> proximos [cocientePerrin n | n <- [3..]] 1e-32

-- [1.324717957244746,1.324717957244746]

-- Esto indica que el límite de la sucesión de cocientes es

-- 1.324717957244746.

-- ---------------------------------------------------------------------

-- Ejercicio 11. Sea p(n) el n-ésimo término de la sucesión de Perrin y

-- q(n)=p(n)/p(n-1) (para n >= 3). Demostrar que el límite de q(n) es

-- una raíz de la ecuación x^3-x-1=0.

-- ---------------------------------------------------------------------

-- Por definición de la sucesión de Perrin, se tiene que

-- P(n) = P(n-2)+P(n-3).

-- Por tanto,

-- P(n)/P(n-1)}

-- = P(n-2)/P(n-1)} + P(n-3)/P(n-2) * P(n-2)/P(n-1)

-- = P(n-2)/P(n-1)} + 1/(P(n-3)/P(n-2)) * 1/(P(n-2)/P(n-1))

-- Sea x el límite de Q(n). Entonces

-- x = 1/x + 1/x^2

-- Por tanto,

-- x^3 = x+1

-- y x es una raíz de x^3-x-1 = 0.

-- ---------------------------------------------------------------------

-- Ejercicio 12. Las raíces de una ecuación pueden aproximarse por el

-- método de bisección que se basa en el siguiente teorema:

-- [Teorema del valor medio] Sea f una función continua en un

-- intervalo [a,b] y supongamos que f(a) y f(b) tienen signos

-- opuestos. Entonces para cada y entre f(a) y f(b), existe un x en

-- [a,b] tal que f(x)=y.

-- El método de bisección consiste en calcular el punto medio del

-- intervalo: m=(a+b)/2. Se consideran tres casos:

-- * si |f(m)| < 10^{-9}, entonces m es una raíz de f(x)=0,

-- * si f(m) tiene el mismo signo que f(a) se repite el procedimiento en

-- el intervalo [m,b],

-- * en otro caso, se repite el procedimiento en el intervalo [a,m].

-- Definir la función

-- biseccion :: (Double -> Double) -> Double -> Double -> Double

-- tal que (biseccion f a b) es la raíz de f en el intervalo [a,b]

-- calculada por el método de bisección. Por ejemplo,

-- biseccion (\x -> x^2-9) 2 5 ==> 3.0000000001164153

-- ---------------------------------------------------------------------

biseccion :: (Double -> Double) -> Double -> Double -> Double

biseccion f a b

| abs (f m) < 1e-9 = m

| signum (f m) == signum (f a) = biseccion f m b

| otherwise = biseccion f a m

where m = (a+b)/2

-- ---------------------------------------------------------------------

-- Ejercicio 13. Calcular por el método de bisección la solución de

-- x^3-x-1=0 en el intervalo [1,2] y compararla con el límite de la

-- sucesión de cocientes de Perrin.

-- ---------------------------------------------------------------------

-- La solución se calcula por

-- ghci> biseccion (\x -> x^3-x-1) 1 2

-- 1.324717957060784

-- Se observa que coincide con el límite de la sucesión de cocientes de Perrin.

Se puede imprimir o compartir con