La sucesión «Mira y di»

PorJosé A. Alonso 24-enero-201731-enero-2017

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")

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]

1	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

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

1	2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

Definir la función

   aproximacionConway :: Integer -> Double -> Int

1	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

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

Nota: Este ejercicio ha sido propuesto por Elías Guisado.

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)

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)

7 Comentarios

import Data.List (foldl')

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi n = n : [(aEntero.lee) x | x <- sucMiraYDi n]
  where
    lee x = concatMap (\xs -> [genericLength xs, head xs])
                      ((group.digitos) x)

digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]

aEntero :: [Integer] -> Integer
aEntero = foldl' (\x y -> 10*x + y) 0 

cteConway :: Double
cteConway = 1.303577269

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e = aux (sucMiraYDi n) e 0
  where
    aux (x:y:xs) e k
      | abs (genericLength (show y) / genericLength (show x) - cteConway) < e
        = k
      | otherwise = aux (y:xs) e (k+1)

import Data.List (foldl')

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi n = n : [(aEntero.lee) x | x <- sucMiraYDi n]

where

lee x = concatMap (\xs -> [genericLength xs, head xs])

((group.digitos) x)

digitos :: Integer -> [Integer]

digitos n = [read [x] | x <- show n]

aEntero :: [Integer] -> Integer

aEntero = foldl' (\x y -> 10*x + y) 0

cteConway :: Double

cteConway = 1.303577269

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e = aux (sucMiraYDi n) e 0

where

aux (x:y:xs) e k

| abs (genericLength (show y) / genericLength (show x) - cteConway) < e

= k

| otherwise = aux (y:xs) e (k+1)

Responder

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi n = n: auxSD (digitos n)
  where auxSD xs =  digitosToInt (define xs) : auxSD (define xs) 

digitos :: Integer -> [Integer]
digitos x = [read [d] | d <- show x]

define :: [Integer] -> [Integer]
define (x:xs) =
  genericLength (takeWhile (==x) (x:xs)) : x : define (dropWhile (==x) xs)
define [] = []

digitosToInt :: [Integer] -> Integer
digitosToInt xs = read (concatMap (show) xs)

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e =
  head [ k | (p,k) <- zip (razones (sucMiraYDi n)) [0..]
           , abs (p - 1.303577269) < e] 

razones :: [Integer] -> [Double]
razones (x:y:xs) =
  ((genericLength (digitos y))/(genericLength (digitos x))) : razones (y:xs)
razones [y] = []

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi n = n: auxSD (digitos n)

where auxSD xs = digitosToInt (define xs) : auxSD (define xs)

digitos :: Integer -> [Integer]

digitos x = [read [d] | d <- show x]

define :: [Integer] -> [Integer]

define (x:xs) =

genericLength (takeWhile (==x) (x:xs)) : x : define (dropWhile (==x) xs)

define [] = []

digitosToInt :: [Integer] -> Integer

digitosToInt xs = read (concatMap (show) xs)

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e =

head [ k | (p,k) <- zip (razones (sucMiraYDi n)) [0..]

, abs (p - 1.303577269) < e]

razones :: [Integer] -> [Double]

razones (x:y:xs) =

((genericLength (digitos y))/(genericLength (digitos x))) : razones (y:xs)

razones [y] = []

Responder

import Data.List (break)
import Data.Char (intToDigit)

sucMiraYDi :: [Integer]
sucMiraYDi = map read (iterate aux "1")
  where
aux :: String -> String
aux  "1"        = aux2 ("1", "")
aux  (x:xs)     = aux2 (break (/=x) (x:xs))

aux2 :: (String, String) -> String
aux2 (x:xs, "") = intToDigit (length (x:xs)) : [x]
aux2 (x:xs, ys) = intToDigit (length (x:xs)) : x : aux ys

cteConway :: Int -> Double
cteConway n = aux n sucMiraYDi
  where
    aux 0 (x:y:xs) = (fromIntegral (l y))/(fromIntegral (l x))
    aux n (x:xs)   = aux (n-1) xs
    l = length.show

import Data.List (break)

import Data.Char (intToDigit)

sucMiraYDi :: [Integer]

sucMiraYDi = map read (iterate aux "1")

where

aux :: String -> String

aux "1" = aux2 ("1", "")

aux (x:xs) = aux2 (break (/=x) (x:xs))

aux2 :: (String, String) -> String

aux2 (x:xs, "") = intToDigit (length (x:xs)) : [x]

aux2 (x:xs, ys) = intToDigit (length (x:xs)) : x : aux ys

cteConway :: Int -> Double

cteConway n = aux n sucMiraYDi

where

aux 0 (x:y:xs) = (fromIntegral (l y))/(fromIntegral (l x))

aux n (x:xs) = aux (n-1) xs

l = length.show

Responder

La de arriba es la solución original cuando propuse el ejercicio y éste estaba en fase alfa de desarrollo.

Acá les dejo la solución para la última versión del problema:

import Data.List (break)
import Data.Char (intToDigit)

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi n = map read (iterate aux1 (show n))
  where
    aux1 :: String -> String
    aux1 (x:xs)     = aux2 (break (/=x) (x:xs))
    aux2 :: (String, String) -> String
    aux2 (x:xs, "") = intToDigit (length (x:xs)) : [x]
    aux2 (x:xs, ys) = intToDigit (length (x:xs)) : x : aux1 ys

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e = aux e 0 (sucMiraYDi n)
  where
    aux e k (x:y:xs)
      | abs ((fromIntegral (l y))/(fromIntegral (l x)) - 1.303577269) < abs e
        = k
      | otherwise = aux e (k+1) (y:xs)
    l = length.show

import Data.List (break)

import Data.Char (intToDigit)

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi n = map read (iterate aux1 (show n))

where

aux1 :: String -> String

aux1 (x:xs) = aux2 (break (/=x) (x:xs))

aux2 :: (String, String) -> String

aux2 (x:xs, "") = intToDigit (length (x:xs)) : [x]

aux2 (x:xs, ys) = intToDigit (length (x:xs)) : x : aux1 ys

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e = aux e 0 (sucMiraYDi n)

where

aux e k (x:y:xs)

| abs ((fromIntegral (l y))/(fromIntegral (l x)) - 1.303577269) < abs e

= k

| otherwise = aux e (k+1) (y:xs)

l = length.show

Responder

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi x = x:sucMiraYDi (read (mira 1 (show x)))

mira :: Int -> String -> String
mira n [x] = [intToDigit n,x]
mira n (x:y:xs) | x == y    = mira (n+1) (y:xs)
                | otherwise = intToDigit n : x : mira 1 (y:xs)

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e =
  aux 0 e (map (fromIntegral.length.show) (sucMiraYDi n))
  where aux n e (x:y:xs)
          | abs ((y/x) - 1.303577269) <= e = n
          | otherwise                      = aux (n+1) e (y:xs)

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi x = x:sucMiraYDi (read (mira 1 (show x)))

mira :: Int -> String -> String

mira n [x] = [intToDigit n,x]

mira n (x:y:xs) | x == y = mira (n+1) (y:xs)

| otherwise = intToDigit n : x : mira 1 (y:xs)

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e =

aux 0 e (map (fromIntegral.length.show) (sucMiraYDi n))

where aux n e (x:y:xs)

| abs ((y/x) - 1.303577269) <= e = n

| otherwise = aux (n+1) e (y:xs)

Responder

import Data.List (group)

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi = fmap read . sucMiraYDiX . show

sucMiraYDiX :: String -> [String]
sucMiraYDiX = iterate (concatMap miraYdi . group)
  where
    miraYdi = (++) <$> show . length <*> take 1

cteConway :: Double
cteConway =  1.303577269

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e = length . takeWhile (>=e)
                       $ zipWith diff xs (tail xs)
  where
    xs = fmap length (sucMiraYDiX (show n))
    diff x y = abs (cteConway - (fromIntegral y / fromIntegral x))

import Data.List (group)

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi = fmap read . sucMiraYDiX . show

sucMiraYDiX :: String -> [String]

sucMiraYDiX = iterate (concatMap miraYdi . group)

where

miraYdi = (++) <$> show . length <*> take 1

cteConway :: Double

cteConway = 1.303577269

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e = length . takeWhile (>=e)

$ zipWith diff xs (tail xs)

where

xs = fmap length (sucMiraYDiX (show n))

diff x y = abs (cteConway - (fromIntegral y / fromIntegral x))

Responder

sucMiraYDi :: Integer -> [Integer]
sucMiraYDi n = n : sucMiraYDi (read $ lee $ show n)

lee :: String -> String
lee []     = []
lee (x:xs) = (show (length (takeWhile (==x) xs) + 1)
             ++ [x]) ++ lee (dropWhile (==x) xs)

razonCifras :: Integer -> Integer -> Double
razonCifras x y =
  fromIntegral (length (show x)) / fromIntegral (length (show y))

conway :: Double
conway = 1.303577269

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n y =
  head [ a  | a <- [0..]
            , let xs = sucMiraYDi n
            , abs (razonCifras (xs!!(a+1)) (xs!!a) - conway) <= y]

sucMiraYDi :: Integer -> [Integer]

sucMiraYDi n = n : sucMiraYDi (read $ lee $ show n)

lee :: String -> String

lee [] = []

lee (x:xs) = (show (length (takeWhile (==x) xs) + 1)

++ [x]) ++ lee (dropWhile (==x) xs)

razonCifras :: Integer -> Integer -> Double

razonCifras x y =

fromIntegral (length (show x)) / fromIntegral (length (show y))

conway :: Double

conway = 1.303577269

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n y =

head [ a | a <- [0..]

, let xs = sucMiraYDi n

, abs (razonCifras (xs!!(a+1)) (xs!!a) - conway) <= y]

Responder

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico