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)

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
-- ===========
 
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)
 
-- 4ª solución
-- ===========
 
sylvester5 :: Integer -> Integer
sylvester5 0 = 2
sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))
 
sucSylvester5 :: [Integer]
sucSylvester5 = map sylvester5 [0..]
 
productosSylvester :: [Integer]
productosSylvester = scanl1 (*) sucSylvester5
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (show (sylvester1 20))
--    213441
--    (3.40 secs, 519,249,840 bytes)
--    λ> length (show (sylvester2 20))
--    213441
--    (0.10 secs, 13,716,024 bytes)
--    λ> length (show (sylvester3 20))
--    213441
--    (0.16 secs, 13,646,472 bytes)
--    λ> length (show (sylvester4 20))
--    213441
--    (0.18 secs, 13,654,064 bytes)
--    λ> length (show (sylvester5 20))
--    213441
--    (0.12 secs, 13,497,192 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. alerodrod5
    import Data.Matrix
    import Graphics.Gnuplot.Simple
     
    sylvester :: Integer -> Integer
    sylvester 0 = 2
    sylvester n = q ! (x,x)
      where x = fromIntegral n
            q = matrix x x f
              where f (i,j)
                      | i == 1 && j == 1 = 3
                      | i == j = product [q ! (a,a) | a <- [1..i-1]] * 2 + 1 
                      | otherwise = 0
     
    ultimosDigitos :: Integer -> Integer -> Integer
    ultimosDigitos n y = y `mod`(10^n)
     
    lista n = map (ultimosDigitos n) (map sylvester [0..]) 
     
    graficaSylvester :: Integer -> Integer -> IO ()
    graficaSylvester n d =
      plotList [Key Nothing]
               (take (fromInteger d) (lista  n))
    • jorcatote

      El resto de funciones me han salido igual, pero la definición de sylvester así es algo más eficiente (y bastante más corta):

      sylvester :: Integer -> Integer
      sylvester n = sylvesterS `genericIndex` n
       
      sylvesterS :: [Integer]
      sylvesterS = iterate (x -> (x-1)*x+1) 2 
       
      -- λ> length (show (sylvester1 25))
      -- 6830085
      -- (7.27 secs, 451,711,704 bytes)
      -- λ> length (show (sylvester2 25))
      -- 6830085
      -- (6.61 secs, 443,069,768 bytes)
      • albcarcas1

        Las otras dos funciones también me han salido igual En la de Sylvester he combinado la de Jorge con programación dinámica y mejora el tiempo.

        import Data.Vector
         
        sylvester :: Integer -> Integer
        sylvester n = v ! y
          where v = iterateN (y+1) (x -> ((x-1)*x)+1)  2
                y = fromInteger n
         
        -- λ> length (show (sylvester3 25))
        -- 6830085
        -- (4.50 secs, 443,070,448 bytes)
  2. agumaragu1
    import Data.Matrix
    import Graphics.Gnuplot.Simple
     
    sylvester :: Integer -> Integer
    sylvester n = (suSylvester (n+1))!(1,n'+1)
      where n' = fromInteger n
     
    suSylvester :: Integer -> Matrix Integer
    suSylvester n = p
      where p = matrix 1 (fromInteger n) f
            f (1,1) = 2
            f (_,j) = ant^2 - ant + 1
              where ant = p!(1,j-1)
     
    graficaSylvester :: Integer -> Integer -> IO ()
    graficaSylvester d n = plotList [Key Nothing] (toList (suSylvester2 d n))
     
    suSylvester2 :: Integer -> Integer -> Matrix Integer
    suSylvester2 d n = p
      where p = matrix 1 (fromInteger n) f
            f (1,1) = 2
            f (_,j) = aux (ant^2 - ant + 1)
              where ant = p!(1,j-1)
            aux x = mod x (10^d)
  3. carbremor

    — Sucesión de Sylvester

    import Graphics.Gnuplot.Simple

    sylvester :: Integer -> Integer
    sylvester 0 = 2
    sylvester n = sylvester m ^ 2 – sylvester m + 1
    where m = n – 1

    — λ> sylvester 8
    — 12864938683278671740537145998360961546653259485195807
    — (0.01 secs, 354,528 bytes)

    ultimosDigitos :: Integer -> Integer -> Integer
    ultimosDigitos n y = y mod(10^n)

    listaGrafica n = map (ultimosDigitos n) (map sylvester [0..])

    graficaSylvester :: Integer -> Integer -> IO ()
    graficaSylvester n d = plotList [Key Nothing]
    (take (fromInteger d) (listaGrafica n))

  4. angruicam1

    Un intento de definición usando coq,

    Fixpoint sylvester (n : nat) : nat :=
      match n with
      | 0    => 2
      | S n' => sylvester n' * (sylvester n' - 1) + 1
      end.

    y la prueba de que a partir del 2 todos los términos de la sucesión son impares.

    Require Import Coq.Arith.Even.
    Require Import Coq.Arith.Plus.
    Require Import Coq.Arith.Minus.
     
    Theorem sylvester_odd : forall (n : nat),
        odd (sylvester (S n)).
    Proof.
      intro n.
      induction n as [| n'].
      - simpl. intuition.
      - simpl. apply even_plus_aux. right. split.
        + apply even_mult_aux. right. rewrite plus_comm, minus_plus.
          inversion IHn' as [n Hn Hn']. rewrite plus_comm in Hn'.
          simpl in Hn'. inversion Hn' as [H]. rewrite H in Hn. apply Hn.
        + intuition.
    Qed.

Escribe tu solución

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