Menu Close

Sucesión de Cantor de números innombrables

 

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

   1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior:

  1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
  24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
  44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
  (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
  (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
  (30) 99 100

Definir las funciones

   sucCantor        :: [Integer]
   graficaSucCantor :: Int -> IO ()

tales que

  • sucCantor es la lista cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,
     λ> take 100 sucCantor
     [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
      22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
      40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
      13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
      20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
      6, 92,93,94,95,96, 29, 30 ,99,100]
     λ> sucCantor2 !! (5+10^6)
     544480
     λ> sucCantor2 !! (6+10^6)
     266086
  • (graficaSucCantor n) es la gráfica de los n primeros términos de la sucesión de Cantor. Por ejemplo, (graficaSucCantor 200) dibuja

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 22 de febrero.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Dices que nada se pierde
y acaso dices verdad;
pero todo lo perdemos
y todo nos perderá.

Antonio Machado

Simplificación de expresiones booleanas

 

El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

   data Expr = X
             | V
             | F
             | Neg Expr
             | Dis Expr Expr
             deriving (Eq, Ord)

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

   valor      :: Expr -> Bool -> Bool 
   simplifica :: Expr -> Expr

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

   valor (Neg X) True           ==  False
   valor (Neg F) True           ==  True
   valor (Dis X (Neg X)) True   ==  True
   valor (Dis X (Neg X)) False  ==  True

y (simplifica p) es una expresión obtenida aplicándole a p las siguientes reglas de simplificación:

   Neg V       = F
   Neg F       = V
   Neg (Neg q) = q
   Dis V q     = V
   Dis F q     = q
   Dis q V     = V
   Dis q F     = F
   Dis q q     = q

Por ejemplo,

   simplifica (Dis X (Neg (Neg X)))                      ==  X
   simplifica (Neg (Dis (Neg (Neg X)) F))                ==  Neg X
   simplifica (Dis (Neg F) F)                            ==  V
   simplifica (Dis (Neg V) (Neg (Dis (Neg X) F)))        ==  X
   simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F)))  ==  Neg X

Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Para la comprobación, de define el generador

   instance Arbitrary Expr where
     arbitrary = sized expr
       where expr n | n < = 0    = atom
                    | otherwise = oneof [ atom
                                        , liftM Neg subexpr
                                        , liftM2 Dis subexpr subexpr ]
               where atom    = oneof [elements [X,V,F]]
                     subexpr = expr (n `div` 2)

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 21 de febrero.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

¿Dices que nada se pierde?
Si esta copa de cristal
se me rompe, nunca en ella
beberé, nunca jamás.

Antonio Machado

Cálculo de pi mediante la serie de Nilakantha

 

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

Definir las funciones

   aproximacionPi :: Int -> Double
   tabla          :: FilePath -> [Int] -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,
     aproximacionPi 0        ==  3.0
     aproximacionPi 1        ==  3.1666666666666665
     aproximacionPi 2        ==  3.1333333333333333
     aproximacionPi 3        ==  3.145238095238095
     aproximacionPi 4        ==  3.1396825396825396
     aproximacionPi 5        ==  3.1427128427128426
     aproximacionPi 10       ==  3.1414067184965018
     aproximacionPi 100      ==  3.1415924109719824
     aproximacionPi 1000     ==  3.141592653340544
     aproximacionPi 10000    ==  3.141592653589538
     aproximacionPi 100000   ==  3.1415926535897865
     aproximacionPi 1000000  ==  3.141592653589787
     pi                      ==  3.141592653589793
  • (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión
     tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero “AproximacionesPi.txt” sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

     tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero “AproximacionesPi.txt” sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 18 de abril.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Bueno es saber que los vasos
nos sirven para beber;
lo malo es que no sabemos
para que sirve la sed.

Antonio Machado

Sucesión de sumas de dos números abundantes

 

Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

   sumasDeDosAbundantes :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

   take 10 sumasDeDosAbundantes  ==  [24,30,32,36,38,40,42,44,48,50]

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 18 de febrero.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

¿Dices que nada se crea?
Alfarero, a tus cacharros.
Haz tu copa y no te importe
si no puedes hacer barro.

Antonio Machado

Particiones de enteros positivos

 

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

   particiones :: Int -> [[Int]]

tal que (particiones n) es la lista de las particiones del número
n. Por ejemplo,

   particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
   particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
   length (particiones 50)  ==  204226

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 18 de febrero.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Fe empirista. Ni somos ni seremos.
Todo nuestro vivir es emprestado.
Nada trajimos, nada llevaremos.

Antonio Machado

Término ausente en una progresión aritmética

 

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

   ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

   ausente [3,7,9,11]               ==  5
   ausente [3,5,9,11]               ==  7
   ausente [3,5,7,11]               ==  9
   ausente ([1..9]++[11..])         ==  10
   ausente ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Soluciones

import Data.List (group, genericLength)
 
-- 1ª solución
ausente1 :: Integral a => [a] -> a
ausente1 (x1:xs@(x2:x3:_))
    | d1 == d2   = ausente1 xs
    | d1 == 2*d2 = x1+d2
    | d2 == 2*d1 = x2+d1
    where d1 = x2-x1
          d2 = x3-x2          
 
-- 2ª definición
ausente2 :: Integral a => [a] -> a
ausente2 s@(x1:x2:x3:xs) 
    | x1+x3 /= 2*x2 = x1+(x3-x2)
    | otherwise = head [a | (a,b) <- zip [x1,x2..] s, a /= b]
 
-- 3ª definición
ausente3 :: Integral a => [a] -> a
ausente3  xs@(x1:x2:_) 
    | null us   = x1 + v
    | otherwise = x2 + u * genericLength (u:us) 
    where ((u:us):(v:_):_) = group (zipWith (-) (tail xs) xs)
 
-- Comparación de eficiencia
--    ghci> let n = 10^6 in ausente1 ([1..n] ++ [n+2])
--    1000001
--    (3.53 secs, 634729880 bytes)
--    
--    ghci> let n = 10^6 in ausente2 ([1..n] ++ [n+2])
--    1000001
--    (0.86 secs, 346910784 bytes)
--    
--    ghci> let n = 10^6 in ausente3 ([1..n] ++ [n+2])
--    1000001
--    (1.22 secs, 501521888 bytes)
--    
--    ghci> let n = 10^7 in ausente2 ([1..n] ++ [n+2])
--    10000001
--    (8.68 secs, 3444142568 bytes)
--    
--    ghci> let n = 10^7 in ausente3 ([1..n] ++ [n+2])
--    10000001
--    (12.59 secs, 4975932088 bytes)

Pensamiento

¡Y esa gran placentería
de ruiseñores que cantan!
Ninguna voz es la mía.

Antonio Machado

Aritmética lunar

 

En la aritmética lunar la suma y el producto se hace como en la terrícola salvo que sus tablas de sumar y de multiplicar son distintas. La suma lunar de dos dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7) y el producto lunar de dos dígitos es su mínimo (por ejemplo, 1 x 3 = 1 y 7 x 4 = 4). Por tanto,

     3 5 7        3 5 7
   +   6 4      x   6 4
   -------      -------
     3 6 7        3 4 4
                3 5 6
                -------
                3 5 6 4

Definir las funciones

   suma     :: Integer -> Integer -> Integer
   producto :: Integer -> Integer -> Integer

tales que

  • (suma x y) es la suma lunar de x e y. Por ejemplo,
     suma 357 64  ==  367
     suma 64 357  ==  367
     suma 1 3     ==  3
     suma 7 4     ==  7
  • (producto x y) es el producto lunar de x e y. Por ejemplo,
     producto 357 64  ==  3564
     producto 64 357  ==  3564
     producto 1 3     ==  1
     producto 7 4     ==  4

Comprobar con QuickCheck que la suma y el producto lunar son conmutativos.

Soluciones

import Test.QuickCheck
 
suma :: Integer -> Integer -> Integer
suma 0 0 = 0
suma x y = max x2 y2 + 10 * suma x1 y1
  where (x1,x2) = x `divMod` 10
        (y1,y2) = y `divMod` 10
 
producto :: Integer -> Integer -> Integer
producto 0 _ = 0
producto x y = productoDigitoNumero x2 y `suma` (10 * producto x1 y)
  where (x1, x2) = x `divMod` 10
 
-- (productoDigitoNumero d x) es el producto del dígito d por el número
-- x. Por ejemplo,
--    productoDigitoNumero 4 357  ==  344
--    productoDigitoNumero 6 357  ==  356
productoDigitoNumero :: Integer -> Integer -> Integer
productoDigitoNumero _ 0 = 0
productoDigitoNumero d x = min d x2 + 10 * productoDigitoNumero d x1
  where (x1, x2) = x `divMod` 10
 
-- La propiedad es
prop_conmutativa :: Positive Integer -> Positive Integer -> Bool
prop_conmutativa (Positive x) (Positive y) =
  suma x y == suma y x &&
  producto x y == producto y x
 
-- La comprobación es
--    λ> quickCheck prop_conmutativa
--    +++ OK, passed 100 tests.

Pensamiento

Cantad conmigo en coro: saber, nada sabemos,
de arcano mar vinimos, a ignota mar iremos …
La luz nada ilumina y el sabio nada enseña.
¿Qué dice la palabra? ¿Qué el agua de la peña?

Antonio Machado

Exterior de árboles

 

Los árboles binarios con datos en loas hojas y los nodos se definen por

   data Arbol = H Int
              | N Int Arbol Arbol 
     deriving Show

Por ejemplo, los árboles

          3               3               3     
         / \             / \             / \    
        /   \           /   \           /   \   
       2     8         2     8         2     8  
      / \   / \       / \   / \       / \   / \ 
     5   7 6   9     5   7 6   9     5   7 6   9
    / \                   / \                 / \   
   1   4                 1   4               1   4

se representan por

   ejArbol1, ejArbol2, ejArbol3 :: Arbol 
   ejArbol1 = N 3
                (N 2 
                   (N 5 (H 1) (H 4))
                   (H 7))
                (N 8 (H 6) (H 9))
   ejArbol2 = N 3
                (N 2 (H 5) (H 7))
                (N 8 (N 6 (H 1) (H 4))
                     (H 9))
   ejArbol3 = N 3
                (N 2 (H 5) (H 7))
                (N 8 (H 6)
                     (N 9 (H 1) (H 4)))

Definir la función

   exterior :: Arbol -> [Int]

tal que (exterior a) es la lista de los elementos exteriores del árbol a. Por ejemplo,

   exterior ejArbol1  ==  [3,2,5,1,4,7,6,9,8]
   exterior ejArbol2  ==  [3,2,5,7,1,4,9,8]
   exterior ejArbol3  ==  [3,2,5,7,6,1,4,9,8]

El orden de los elementos es desde la raíz hasta el extremo inferior izquierdo desde él hasta el inferior derecho y desde él hasta la raíz.

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol 
  deriving Show
 
ejArbol1, ejArbol2, ejArbol3 :: Arbol 
ejArbol1 = N 3
             (N 2 
                (N 5 (H 1) (H 4))
                (H 7))
             (N 8 (H 6) (H 9))
ejArbol2 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (N 6 (H 1) (H 4))
                  (H 9))
ejArbol3 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (H 6)
                  (N 9 (H 1) (H 4)))
 
exterior :: Arbol -> [Int]
exterior a =
  ramaIzquierda a ++ hojas a ++ reverse (tail (ramaDerecha a))
 
-- (ramaIzquierda a) es la rama izquierda del árbol a. Por ejemplo,
--    ramaIzquierda ejArbol1  ==  [3,2,5]
--    ramaIzquierda ejArbol3  ==  [3,2]
ramaIzquierda :: Arbol -> [Int]
ramaIzquierda (H _)     = []
ramaIzquierda (N x i _) = x : ramaIzquierda i
 
-- (ramaDerecha a) es la rama derecha del árbol a. Por ejemplo,
--    ramaDerecha ejArbol1  ==  [3,8]
--    ramaDerecha ejArbol3  ==  [3,8,9]
ramaDerecha :: Arbol -> [Int]
ramaDerecha (H _)     = []
ramaDerecha (N x _ d) = x : ramaDerecha d
 
-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,
--    hojas ejArbol1  ==  [1,4,7,6,9]
--    hojas ejArbol3  ==  [5,7,6,1,4]
hojas :: Arbol -> [Int]
hojas (H x)     = [x]
hojas (N _ i d) = hojas i ++ hojas d

Pensamiento

¿Dónde está la utilidad
de nuestras utilidades?
Volvamos a la verdad:
vanidad de vanidades.

Antonio Machado

Medias de dígitos de pi

 

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

   mediasDigitosDePi        :: IO [Double]
   graficaMediasDigitosDePi :: Int -> IO ()

tales que

  • mediasDigitosDePi es la sucesión cuyo n-ésimo elemento es la media de los n primeros dígitos de pi. Por ejemplo,
     λ> xs <- mediasDigitosDePi
     λ> take 5 xs
     [1.0,2.5,2.0,2.75,4.0]
     λ> take 10 xs
     [1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
     λ> take 10 <$> mediasDigitosDePi
     [1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
  • (graficaMediasDigitosDePi n) dibuja la gráfica de los n primeros términos de mediasDigitosDePi. Por ejemplo,
    • (graficaMediasDigitosDePi 20) dibuja
    • (graficaMediasDigitosDePi 200) dibuja
    • (graficaMediasDigitosDePi 2000) dibuja

Soluciones

import Data.Char (digitToInt)
import Data.List (genericLength, inits, tails)
import Graphics.Gnuplot.Simple ( Attribute (Key, PNG)
                               , plotList )
 
-- Definición de mediasDigitosDePi
-- ===============================
 
mediasDigitosDePi :: IO [Double]
mediasDigitosDePi = do
  (_:_:ds) <- readFile "Digitos_de_pi.txt"
  return (medias (digitos ds))
 
-- (digitos cs) es la lista de los digitos de cs. Por ejempplo,
--    digitos "1415926535"  ==  [1,4,1,5,9,2,6,5,3,5]
digitos :: String -> [Int]
digitos = map digitToInt
 
-- (medias xs) es la lista de las medias de los segmentos iniciales de
-- xs. Por ejemplo,
--    λ> medias [1,4,1,5,9,2,6,5,3,5]
--    [1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
medias :: [Int] -> [Double]
medias xs = map media (tail (inits xs))
 
-- (media xs) es la media aritmética de xs. Por ejemplo,
--    media [1,4,1,5,9]  ==  4.0
media :: [Int] -> Double
media xs = fromIntegral (sum xs) / genericLength xs
 
-- Definición de graficaMediasDigitosDePi
-- ======================================
 
graficaMediasDigitosDePi :: Int -> IO ()
graficaMediasDigitosDePi n = do
  xs <- mediasDigitosDePi
  plotList [ Key Nothing
           , PNG ("Medias_de_digitos_de_pi_" ++ show n ++ ".png")
           ]
           (take n xs)

Pensamiento

Es el mejor de los buenos
quien sabe que en esta vida
todo es cuestión de medida:
un poco más, algo menos.

Antonio Machado

Límites de sucesiones

 

El límite de una sucesión, con una aproximación a y una amplitud n, es 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.

Definir la función

   limite :: [Double] -> Double -> Int -> Double

tal que (limite xs a n) es el límite de xs xon aproximación a y amplitud n. 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

Soluciones

import Data.List (tails)
 
limite :: [Double] -> Double -> Int -> Double
limite 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)

Pensamiento

De diez cabezas, nueve
embisten y una piensa.
Nunca extrañéis que un bruto
se descuerne luchando por la idea.

Antonio Machado