La sucesión "Mira y di"
La sucesión "Mira y di" (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como "un uno" y por tanto x(1) = 11. Análogamente,
x(1) = 11 (dos unos --> 21) x(2) = 21 (un dos un uno --> 1211) x(3) = 1211 (un uno un dos dos unos --> 111221) x(4) = 111221 (tres unos dos doses un uno --> 312211) x(5) = 312211 (un tres un uno dos doses dos unos --> 13112221)
Definir la función
sucMiraYDi :: Integer -> [Integer]
tal que (sucMiraYDi n) es la sucesión "Mira y di" cuyo primer término es n. Por ejemplo,
λ> take 9 (sucMiraYdi 1) [1,11,21,1211,111221,312211,13112221,1113213211,31131211131221] λ> take 5 (sucMiraYdi 2017) [2017,12101117,111211103117,31123110132117,1321121321101113122117] λ> take 7 (sucMiraYDi 22) [22,22,22,22,22,22,22] λ> (sucMiraYDi 1) !! 11 3113112221232112111312211312113211 λ> (sucMiraYDi 1) !! 12 1321132132111213122112311311222113111221131221
Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son
2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3
Definir la función
aproximacionConway :: Integer -> Double -> Int
tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,
aproximacionConway 1 0.3 == 3 aproximacionConway 1 0.1 == 5 aproximacionConway 1 0.01 == 9 aproximacionConway 1 0.001 == 24 aproximacionConway 1 0.0001 == 43 aproximacionConway 2 0.0001 == 47
Soluciones
import Data.List (genericLength, group) -- 1ª solución -- =========== sucMiraYdi :: Integer -> [Integer] sucMiraYdi = iterate di -- (di x) es el número correspondiente a la lectura de x. Por ejemplo. -- di 1 == 11 -- di 11 == 21 -- di 21 == 1211 -- di 1211 == 111221 -- di 111221 == 312211 -- di 312211 == 13112221 di :: Integer -> Integer di = read . concatMap aux . group . show where aux s = show (length s) ++ [head s] -- 2ª solución -- =========== sucMiraYdi2 :: Integer -> [Integer] sucMiraYdi2 = iterate (read . concatMap aux . group . show) where aux s = show (length s) ++ [head s] -- Constante de Conway -- =================== aproximacionConway :: Integer -> Double -> Int aproximacionConway n e = length (takeWhile aux (razonesMiraYdi n)) where aux x = abs (x - constanteConway) > e constanteConway :: Double constanteConway = 1.303577269 -- (razonesMiraYdi n) es la sucesión de las razones entre de cada -- elemento de la sucesión "Mira y di" con elemento inicial n y su -- anterior. Por ejemplo, -- λ> take 10 (razonesMiraYdi 1) -- [2.0,1.0,2.0,1.5,1.0,1.3333333333333333,1.25,1.4,1.4285714285714286,1.3] -- λ> take 7 (razonesMiraYdi 10) -- [2.0,1.0,1.5,1.6666666666666667,1.2,1.1666666666666667,1.5714285714285714] razonesMiraYdi :: Integer -> [Double] razonesMiraYdi n = zipWith (/) (tail xs) xs where xs = map (genericLength . show) (sucMiraYdi n)