Menu Close

La sucesión de Sylvester

José A. Alonso,

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 ()

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
  • (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
      La_sucesion_de_Sylvester_(3,30)
    • (graficaSylvester 4 30) dibuja
      La_sucesion_de_Sylvester_(4,30)
    • (graficaSylvester 5 30) dibuja
      La_sucesion_de_Sylvester_(5,30)

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]]
Medio
, , , , , , , , , , , , ,

6 soluciones de “La sucesión de Sylvester”

  1. Responder
    anthormol 
    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]]
  2. Responder
    fercarnav 
    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]]
  3. Responder
    rebgongor

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

    sylvester :: Integer -> Integer
sylvester 0 = 2
sylvester n = sylvester (n-1) * (sylvester (n-1) - 1) + 1
  4. Responder
    Enrique Zubiría 
    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))
  5. Responder
    javjimord 
    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))
  6. Responder
    alvdomgut 
    --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]]

Escribe tu solución

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