El número de Dottie
La sucesión de Dottie correspondiente a un número x se obtiene a partir de x aplicándole la función coseno al término anterior. Por ejemplo, empezando en el 2021 los términos de la sucesión de Dottie son
d(0) = 2021 d(1) = cos(2021) = -0.5768544484396986 d(2) = cos(-0.5768544484396986) = 0.8381823464377144 d(3) = cos(0.8381823464377144) = 0.6688152257126013 d(4) = cos(0.6688152257126013) = 0.7845568438177061 d(5) = cos(0.7845568438177061) = 0.7077014336446841 d(6) = cos(0.7077014336446841) = 0.7598581544800473 d(7) = cos(0.7598581544800473) = 0.7249337238692606 d(8) = cos(0.7249337238692606) = 0.7485433703735275
Definir las funciones
sucesionDottie :: Double -> [Double] limite :: [Double] -> Double -> Int -> Double
tales que
- (sucesionDottie x) es la lista de los términos de la sucesión de Dottie correspondiente a x. Por ejemplo,
λ> mapM_ print (take 10 (sucesionDottie 2021)) 2021.0 -0.5768544484396986 0.8381823464377144 0.6688152257126013 0.7845568438177061 0.7077014336446841 0.7598581544800473 0.7249337238692606 0.7485433703735275 0.7326809874975466 λ> mapM_ print (take 10 (drop 85 (sucesionDottie 2021))) 0.7390851332151601 0.739085133215161 0.7390851332151605 0.7390851332151608 0.7390851332151606 0.7390851332151607 0.7390851332151607 0.7390851332151607 0.7390851332151607 0.7390851332151607
- (limite xs a n) es el límite de xs con aproximación a y amplitud n; es decir, el primer término x de la sucesión tal que el valor absoluto de x y cualquiera de sus n siguentes elementos es menor que a. Por ejemplo,
λ> limite [(2*n+1)/(n+5) | n <- [1..]] 0.001 300 1.993991989319092 λ> limite [(2*n+1)/(n+5) | n <- [1..]] 1e-6 300 1.9998260062637745 λ> limite [(1+1/n)**n | n <- [1..]] 0.001 300 2.7155953364173175 λ> limite (sucesionDottie 2021) 1e-16 100 0.7390851332151607 λ> limite (sucesionDottie 27) 1e-16 100 0.7390851332151607
Comprobar con QuickCheck que, para todo número x, el límite de la sucesión de Dottie generada por x es mismo; es decir, si x e y son dos números cualesquiera, entonces
limite (sucesionDottie x) 1e-16 100 == limite (sucesionDottie y) 1e-16 100
Dicho límite es el número de Dottie.
Referencia: Este ejercicio está basado en el artículo El número de Dottie publicado por Miguel Ángel Morales en Gaussianos el 20 de enero de 2021.
Soluciones
import Data.List (tails) import Test.QuickCheck -- 1ª definición de sucesionDottie -- =============================== sucesionDottie1 :: Double -> [Double] sucesionDottie1 x = map (terminoDottie x) [0..] terminoDottie :: Double -> Int -> Double terminoDottie x 0 = x terminoDottie x n = cos (terminoDottie x (n-1)) -- 2ª definición de sucesionDottie -- =============================== sucesionDottie2 :: Double -> [Double] sucesionDottie2 x = iterate cos x -- Comparación de eficiencia de definiciones de sucesionDottie -- =========================================================== -- La comparación es -- λ> sucesionDottie1 2021 !! (5*10^6) -- 0.7390851332151607 -- (2.13 secs, 1,894,864,000 bytes) -- λ> sucesionDottie2 2021 !! (5*10^6) -- 0.7390851332151607 -- (0.95 secs, 644,703,256 bytes) -- En lo que sigue, usaremos la 2ª definición sucesionDottie :: Double -> [Double] sucesionDottie = sucesionDottie2 -- 1ª definición de limite -- ======================= limite1 :: [Double] -> Double -> Int -> Double limite1 xs a n = head [ x | (x:ys) <- segmentos xs n , all (\y -> abs (y - x) < a) ys] -- (segmentos xs n) es la lista de los segmentos de la lista infinita xs -- con n elementos. Por ejemplo, -- λ> take 5 (segmentos [1..] 3) -- [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]] segmentos :: [a] -> Int -> [[a]] segmentos xs n = map (take n) (tails xs) -- 2ª solución -- =========== limite2 :: [Double] -> Double -> Int -> Double limite2 (n:ns) x a | abs (n - maximum (take (a-1) ns)) < x = n | otherwise = limite2 ns x a -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> limite1 [(1+1/n)**n | n <- [1..]] 1e-8 100 -- 2.7182700737511185 -- (1.40 secs, 1,044,694,328 bytes) -- λ> limite2 [(1+1/n)**n | n <- [1..]] 1e-8 100 -- 2.7182700737511185 -- (0.47 secs, 1,185,073,072 bytes) -- En lo que sigue, usaremos la 2ª definición limite :: [Double] -> Double -> Int -> Double limite = limite2 -- Propiedad -- ========= -- La propiedad es prop_Dottie :: Double -> Double -> Bool prop_Dottie x y = limite (sucesionDottie x) 1e-16 100 == limite (sucesionDottie y) 1e-16 100 -- La comprobación es -- λ> quickCheck prop_Dottie -- +++ OK, passed 100 tests.