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
|
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,
|
1 2 3 4 |
λ> [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
- (graficaSylvester 3 30) dibuja
Nota: Se puede usar programación dinámica para aumentar la eficiencia.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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]] |