Menu Close

La sucesión de Sylvester

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

6 soluciones de “La sucesión de Sylvester

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

Leave a Reply

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