La sucesión de Sylvester

PorJosé A. Alonso 6-mayo-202013-mayo-2020

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

   sylvester        :: Integer -> Integer
   graficaSylvester :: Integer -> Integer -> IO ()

1 2	sylvester :: Integer -> Integer graficaSylvester :: Integer -> Integer -> IO ()

tales que

(sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

     λ> [sylvester n | n <- [0..7]]
     [2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
     λ> length (show (sylvester 25))
     6830085

λ> [sylvester n | n <- [0..7]]

[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]

λ> length (show (sylvester 25))

6830085

(graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
- (graficaSylvester 3 30) dibuja
- (graficaSylvester 4 30) dibuja
- (graficaSylvester 5 30) dibuja

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Soluciones

import Data.List               (genericIndex)
import Data.Array              ((!), array)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)
-- ===========================

sylvester1 :: Integer -> Integer
sylvester1 0 = 2
sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)
-- =======================================

sylvester2 :: Integer -> Integer
sylvester2 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución
-- ===========

-- Observando que
--    S(n) = 1 + S(0)*S(1)*...*S(n-2)*S(n-1)
--         = 1 + (1 + S(0)*S(1)*...*S(n-2))*S(n-1) - S(n-1)
--         = 1 + S(n-1)*S(n-1) - S(n-1)
--         = 1 + S(n-1)^2 - S(n-1)
-- se obtiene la siguiente definición.
sylvester3 :: Integer -> Integer
sylvester3 0 = 2
sylvester3 n = 1 + x^2 - x
  where x = sylvester3 (n-1)

-- 4ª solución
-- ===========

sylvester4 :: Integer -> Integer
sylvester4 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + x^2 - x
    where x = v ! (m-1)

-- 5ª solución
-- ===========

sylvester5 :: Integer -> Integer
sylvester5 n = sucSylvester5 `genericIndex` n

sucSylvester5 :: [Integer]
sucSylvester5 = iterate (\x -> (x-1)*x+1) 2 

-- La comparación es
--    λ> length (show (sylvester1 23))
--    1707522
--    (6.03 secs, 4,090,415,704 bytes)
--    λ> length (show (sylvester2 23))
--    1707522
--    (0.33 secs, 109,477,296 bytes)
--    λ> length (show (sylvester3 23))
--    1707522
--    (0.35 secs, 109,395,136 bytes)
--    λ> length (show (sylvester4 23))
--    1707522
--    (0.33 secs, 109,402,440 bytes)
--    λ> length (show (sylvester5 23))
--    1707522
--    (0.30 secs, 108,676,256 bytes)

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n =
  plotList [ Key Nothing
           , PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")
           ]
           [sylvester5 k `mod` (10^d) | k <- [0..n]]

import Data.List (genericIndex)

import Data.Array ((!), array)

import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)

-- ===========================

sylvester1 :: Integer -> Integer

sylvester1 0 = 2

sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)

-- =======================================

sylvester2 :: Integer -> Integer

sylvester2 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución

-- ===========

-- Observando que

-- S(n) = 1 + S(0)*S(1)*...*S(n-2)*S(n-1)

-- = 1 + (1 + S(0)*S(1)*...*S(n-2))*S(n-1) - S(n-1)

-- = 1 + S(n-1)*S(n-1) - S(n-1)

-- = 1 + S(n-1)^2 - S(n-1)

-- se obtiene la siguiente definición.

sylvester3 :: Integer -> Integer

sylvester3 0 = 2

sylvester3 n = 1 + x^2 - x

where x = sylvester3 (n-1)

-- 4ª solución

-- ===========

sylvester4 :: Integer -> Integer

sylvester4 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + x^2 - x

where x = v ! (m-1)

-- 5ª solución

-- ===========

sylvester5 :: Integer -> Integer

sylvester5 n = sucSylvester5 `genericIndex` n

sucSylvester5 :: [Integer]

sucSylvester5 = iterate (\x -> (x-1)*x+1) 2

-- La comparación es

-- λ> length (show (sylvester1 23))

-- 1707522

-- (6.03 secs, 4,090,415,704 bytes)

-- λ> length (show (sylvester2 23))

-- 1707522

-- (0.33 secs, 109,477,296 bytes)

-- λ> length (show (sylvester3 23))

-- 1707522

-- (0.35 secs, 109,395,136 bytes)

-- λ> length (show (sylvester4 23))

-- 1707522

-- (0.33 secs, 109,402,440 bytes)

-- λ> length (show (sylvester5 23))

-- 1707522

-- (0.30 secs, 108,676,256 bytes)

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n =

plotList [ Key Nothing

, PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")

]

[sylvester5 k `mod` (10^d) | k <- [0..n]]

6 Comentarios

import Data.Array
import Graphics.Gnuplot.Simple

sylvester :: Integer -> Integer
sylvester n = v ! n
  where v = array (0,n) [(i,f i) | i <- [0..n]]
        f 0 = 2
        f n = product [v ! y | y <- [0..n-1]] + 1

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n = 
  plotList [Key Nothing,
            Title ((show d) ++ " digitos sylvester " ++ (show n))]
           xs
    where xs = map (`mod` 10^d) [sylvester n | n <- [1..n]]

import Data.Array

import Graphics.Gnuplot.Simple

sylvester :: Integer -> Integer

sylvester n = v ! n

where v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f n = product [v ! y | y <- [0..n-1]] + 1

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n =

plotList [Key Nothing,

Title ((show d) ++ " digitos sylvester " ++ (show n))]

where xs = map (`mod` 10^d) [sylvester n | n <- [1..n]]

Responder

import Data.Array
import Graphics.Gnuplot.Simple

sylvesterA2 :: Integer -> Integer
sylvesterA2 0 = 2
sylvesterA2 n = vectorSyl (m) ! (0,m)
  where m = fromInteger n
                         
vectorSyl :: Int -> Array (Int,Int) Integer
vectorSyl n = v
  where v = array ((0,0),(1,n)) [((i,j),f i j) | i <- [0,1], j <- [0..n]]
        f _ 0 = 2
        f 0 y = v ! (1,(y-1)) + 1
        f 1 y = v ! (1,(y-1)) * v ! (0, y)

graficaSylvesterA2 :: Integer -> Integer -> IO ()
graficaSylvesterA2 d n = 
  plotList [Key Nothing,
            Title ((show d) ++ " digitos sylvesterA2 " ++ (show n))]
           xs
    where xs = map (`mod` 10^d) (listaSylvesterA2 n)

listaSylvesterA2 :: Integer -> [Integer]
listaSylvesterA2 m = elems (filaMat 0 n (vectorSyl n))
  where n = fromInteger m

filaMat :: Num a => Int -> Int -> Array (Int,Int)  a -> Array Int  a
filaMat i n p = array (0,n) [(j,p!(i,j)) | j <- [0..n]]

import Data.Array

import Graphics.Gnuplot.Simple

sylvesterA2 :: Integer -> Integer

sylvesterA2 0 = 2

sylvesterA2 n = vectorSyl (m) ! (0,m)

where m = fromInteger n

vectorSyl :: Int -> Array (Int,Int) Integer

vectorSyl n = v

where v = array ((0,0),(1,n)) [((i,j),f i j) | i <- [0,1], j <- [0..n]]

f _ 0 = 2

f 0 y = v ! (1,(y-1)) + 1

f 1 y = v ! (1,(y-1)) * v ! (0, y)

graficaSylvesterA2 :: Integer -> Integer -> IO ()

graficaSylvesterA2 d n =

plotList [Key Nothing,

Title ((show d) ++ " digitos sylvesterA2 " ++ (show n))]

where xs = map (`mod` 10^d) (listaSylvesterA2 n)

listaSylvesterA2 :: Integer -> [Integer]

listaSylvesterA2 m = elems (filaMat 0 n (vectorSyl n))

where n = fromInteger m

filaMat :: Num a => Int -> Int -> Array (Int,Int) a -> Array Int a

filaMat i n p = array (0,n) [(j,p!(i,j)) | j <- [0..n]]

Responder

rebgongor dice:

6-mayo-2020 a las 11:15

Definición de la primera función por recursión:

Haskell

sylvester :: Integer -> Integer sylvester 0 = 2 sylvester n = sylvester (n-1) * (sylvester (n-1) - 1) + 1

1
2
3

sylvester :: Integer -> Integer
sylvester 0 = 2
sylvester n = sylvester (n-1) * (sylvester (n-1) - 1) + 1

Responder

import Graphics.Gnuplot.Simple

sucSylvester     :: [Integer]
sucSylvester = 2:map (\x -> x*(x-1)+1) sucSylvester

sylvester        :: Integer -> Integer
sylvester n = head $ drop (fromIntegral n) sucSylvester

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n = do
  plotList [ Key Nothing
           , PNG "sucesionDeSylvester.png"
           ]
           (map (`rem` 10^d) (take (fromIntegral n) sucSylvester))

import Graphics.Gnuplot.Simple

sucSylvester :: [Integer]

sucSylvester = 2:map (\x -> x*(x-1)+1) sucSylvester

sylvester :: Integer -> Integer

sylvester n = head $ drop (fromIntegral n) sucSylvester

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n = do

plotList [ Key Nothing

, PNG "sucesionDeSylvester.png"

]

(map (`rem` 10^d) (take (fromIntegral n) sucSylvester))

Responder

import Data.Array
import Graphics.Gnuplot.Simple

--sylvesterP n es un vector cuyas componentes son los elementos de la sucesión de Sylvester hasta el término n

sylvesterP :: Integer -> Array Integer Integer
sylvesterP n = p where
  p = array (0,n) [(i, f i) | i <- [0..n]]
  f 0 = 2
  f n = f (n-1) * (f (n-1) - 1) + 1
        

sylvester :: Integer -> Integer
sylvester n = last $ elems (sylvesterP n)

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n = do
  plotList [ Key Nothing
           , PNG "sucesionDeSylvester.png"
           ]
           (map (`mod` 10^d) (elems $ sylvesterP n))

import Data.Array

import Graphics.Gnuplot.Simple

--sylvesterP n es un vector cuyas componentes son los elementos de la sucesión de Sylvester hasta el término n

sylvesterP :: Integer -> Array Integer Integer

sylvesterP n = p where

p = array (0,n) [(i, f i) | i <- [0..n]]

f 0 = 2

f n = f (n-1) * (f (n-1) - 1) + 1

sylvester :: Integer -> Integer

sylvester n = last $ elems (sylvesterP n)

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n = do

plotList [ Key Nothing

, PNG "sucesionDeSylvester.png"

]

(map (`mod` 10^d) (elems $ sylvesterP n))

Responder

--Librerías:

import Data.Array
import Graphics.Gnuplot.Simple


--La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes
--términos se obtienen multiplicando los anteriores y sumándole 1.

--Definamos la función sylvester tal que sylvester n es el n-ésimo término de
--dicha sucesión:

--Para ello vamos a usar la técnica de programación dinámica vista hoy
--(6 de mayo de 2020) en clase. 

--Veamos una primera implementación recursiva:

sylvesterRec :: Integer -> Integer
sylvesterRec 0 = 2
sylvesterRec n = 1 + product [sylvesterRec k | k<-[0..n-1]]

--Ahora usemos la programación dinámica:

sylvester :: Integer -> Integer
sylvester n = (vectorSylvester n) ! n


vectorSylvester :: Integer -> Array Integer Integer
vectorSylvester n = v where
  v = array (0,n) [(i, f i) | i<- [0..n]] -- f es la función que calcula cada
                                          -- elemento de la sucesión sylvester 
  f 0 = 2
  f n = product [v ! k | k<-[0..n-1]] + 1


-- Ahora hagamos la gráfica
-- graficaSylvester d n dibuja la gráfica de los d últimos dígitos de los n
-- primeros términos de la sucesión de Sylvester


graficaSylvester :: Integer -> Integer -> IO()
graficaSylvester d n = plotList [Title "La funcion sylvester"] (listaDigitos)
  where listaDigitos = [rem (sylvester n) 10^d | n<-[0..n-1]]

--Librerías:

import Data.Array

import Graphics.Gnuplot.Simple

--La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes

--términos se obtienen multiplicando los anteriores y sumándole 1.

--Definamos la función sylvester tal que sylvester n es el n-ésimo término de

--dicha sucesión:

--Para ello vamos a usar la técnica de programación dinámica vista hoy

--(6 de mayo de 2020) en clase.

--Veamos una primera implementación recursiva:

sylvesterRec :: Integer -> Integer

sylvesterRec 0 = 2

sylvesterRec n = 1 + product [sylvesterRec k | k<-[0..n-1]]

--Ahora usemos la programación dinámica:

sylvester :: Integer -> Integer

sylvester n = (vectorSylvester n) ! n

vectorSylvester :: Integer -> Array Integer Integer

vectorSylvester n = v where

v = array (0,n) [(i, f i) | i<- [0..n]] -- f es la función que calcula cada

-- elemento de la sucesión sylvester

f 0 = 2

f n = product [v ! k | k<-[0..n-1]] + 1

-- Ahora hagamos la gráfica

-- graficaSylvester d n dibuja la gráfica de los d últimos dígitos de los n

-- primeros términos de la sucesión de Sylvester

graficaSylvester :: Integer -> Integer -> IO()

graficaSylvester d n = plotList [Title "La funcion sylvester"] (listaDigitos)

where listaDigitos = [rem (sylvester n) 10^d | n<-[0..n-1]]

Responder

La sucesión de Sylvester

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico