sqrt

Codificación matricial

PorJosé A. Alonso 21-marzo-201729-marzo-2017

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
Se extiende el mensaje con N²-L asteriscos. En el ejemplo, el mensaje extendido es "todoparanada****"
Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

     | t o d o |
     | p a r a |
     | n a d a |
     | * * * * |

| t o d o |

| p a r a |

| n a d a |

| * * * * |

Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

     | * n p t |
     | * a a o |
     | * d r d |
     | * a a o |

| * n p t |

| * a a o |

| * d r d |

| * a a o |

Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "*npt*aap*drd*aao"
El mensaje codificado se obtiene eliminando los asteriscos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

   codificado :: String -> String

1	codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

   codificado "todoparanada"    ==  "nptaaodrdaao"
   codificado "nptaaodrdaao"    ==  "danaopadtora"
   codificado "danaopadtora"    ==  "todoparanada"
   codificado "entodolamedida"  ==  "dmdeaeondltiao"

codificado "todoparanada" == "nptaaodrdaao"

codificado "nptaaodrdaao" == "danaopadtora"

codificado "danaopadtora" == "todoparanada"

codificado "entodolamedida" == "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Soluciones

import Data.List (genericLength)
import Data.Array

codificado :: String -> String
codificado cs =
  filter (/='*') (elems (rota p))
  where n = ceiling (sqrt (genericLength cs))
        p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char
rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]
  where d = bounds p
        n = fst (snd d)

import Data.List (genericLength)

import Data.Array

codificado :: String -> String

codificado cs =

filter (/='*') (elems (rota p))

where n = ceiling (sqrt (genericLength cs))

p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char

rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]

where d = bounds p

n = fst (snd d)

Números de Catalan

PorJosé A. Alonso 13-marzo-201726-marzo-2022

Los números de Catalan forman la sucesión cuyo término general es

Los primeros números de Catalan son

   1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

1	1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

Los números de Catalan satisfacen la siguiente relación de recurrencia:

Asintóticamente, los números de Catalan crecen como:

considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

   catalan :: [Integer]
   grafica :: Int -> Int -> IO ()

1 2	catalan :: [Integer] grafica :: Int -> Int -> IO ()

tales que

catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,

     λ> take 12 catalan
     [1,1,2,5,14,42,132,429,1430,4862,16796,58786]
     λ> length (show (catalan !! 50000))
     30096

λ> take 12 catalan

[1,1,2,5,14,42,132,429,1430,4862,16796,58786]

λ> length (show (catalan !! 50000))

30096

(grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de

Por ejemplo, (grafica 5 10) dibuja

y (grafica 55 60) dibuja

Soluciones

import Graphics.Gnuplot.Simple

catalan :: [Integer]
catalan = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]

grafica :: Int -> Int -> IO ()
grafica a b = 
  plotLists [Key Nothing]
            [[(fromIntegral n, fromIntegral (catalan !! n)) | n <- [a..b]]
            ,[(n,4**n/(n**(3/2)*(sqrt pi))) | n <- [c..d]]]
  where c, d :: Double
        c = fromIntegral a
        d = fromIntegral b

import Graphics.Gnuplot.Simple

catalan :: [Integer]

catalan = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]

grafica :: Int -> Int -> IO ()

grafica a b =

plotLists [Key Nothing]

[[(fromIntegral n, fromIntegral (catalan !! n)) | n <- [a..b]]

,[(n,4**n/(n**(3/2)*(sqrt pi))) | n <- [c..d]]]

where c, d :: Double

c = fromIntegral a

d = fromIntegral b

Caminos minimales en un arbol numérico

PorJosé A. Alonso 10-marzo-201725-abril-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

1	ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

λ> putStrLn (drawTree (fmap show ej))

+- 5

| |

| `- 9

`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

/ \

5 3

| |

4 2

/ \ |

3 2 1

| |

2 1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

mayoresDivisores :: Int -> [Int]

arbol :: Int -> Tree Int

caminos :: Int -> [[Int]]

caminosMinimales :: Int -> [[Int]]

tales que

(mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []

mayoresDivisores 24 == [12,8,6]

mayoresDivisores 16 == [8,4]

mayoresDivisores 10 == [5]

mayoresDivisores 17 == []

(arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1

λ> putStrLn (drawTree (fmap show (arbol 6)))

+- 5

| |

| `- 4

| |

| +- 3

| | |

| | `- 2

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 3

`- 2

`- 1

(caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

1 2	λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

(caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

λ> caminosMinimales 6

[[6,3,2,1]]

λ> caminosMinimales 17

[[17,16,4,2,1]]

λ> caminosMinimales 50

[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree

mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  

arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol

--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

import Data.Tree

mayoresDivisores :: Int -> [Int]

mayoresDivisores x =

[max u v | u <- [2..floor (sqrt (fromIntegral x))]

, x `mod` u == 0

, let v = x `div` u]

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]

caminos = caminosArbol . arbol

-- λ> caminosArbol (arbol 6)

-- [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

caminosArbol :: Tree a -> [[a]]

caminosArbol (Node x []) = [[x]]

caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]

caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [ys | ys <- yss, length ys == m]

where yss = caminos x

m = minimum (map length yss)

Cálculo de pi usando la fórmula de Vieta

PorJosé A. Alonso 14-febrero-201725-abril-2021

La fórmula de Vieta para el cálculo de pi es la siguiente

Definir las funciones

   aproximacionPi :: Int -> Double
   errorPi :: Double -> Int

1 2	aproximacionPi :: Int -> Double errorPi :: Double -> Int

tales que

(aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,

     aproximacionPi  5  ==  3.140331156954753
     aproximacionPi 10  ==  3.1415914215112
     aproximacionPi 15  ==  3.141592652386592
     aproximacionPi 20  ==  3.1415926535886207
     aproximacionPi 25  ==  3.141592653589795

aproximacionPi 5 == 3.140331156954753

aproximacionPi 10 == 3.1415914215112

aproximacionPi 15 == 3.141592652386592

aproximacionPi 20 == 3.1415926535886207

aproximacionPi 25 == 3.141592653589795

(errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1        ==  2
     errorPi 0.01       ==  4
     errorPi 0.001      ==  6
     errorPi 0.0001     ==  7
     errorPi 1e-4       ==  7
     errorPi 1e-14      ==  24
     pi                 ==  3.141592653589793
     aproximacionPi 24  ==  3.1415926535897913

errorPi 0.1 == 2

errorPi 0.01 == 4

errorPi 0.001 == 6

errorPi 0.0001 == 7

errorPi 1e-4 == 7

errorPi 1e-14 == 24

pi == 3.141592653589793

aproximacionPi 24 == 3.1415926535897913

Soluciones

-- 1ª definición de aproximacionPi
aproximacionPi :: Int -> Double
aproximacionPi n = product [2 / aux x | x <- [0..n]]
  where
    aux 0 = 1
    aux 1 = sqrt 2
    aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi
aproximacionPi2 :: Int -> Double
aproximacionPi2 n = product [2/x | x <- 1 : xs] 
  where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi
aproximacionPi3 :: Int -> Double
aproximacionPi3 n =  product (2 : take n (map (2/) xs))
  where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi
errorPi :: Double -> Int
errorPi x = head [n | n <- [1..]
                    , abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi
errorPi2 :: Double -> Int
errorPi2 x = until aceptable (+1) 1
  where aceptable n = abs (pi - aproximacionPi n) < x

-- 1ª definición de aproximacionPi

aproximacionPi :: Int -> Double

aproximacionPi n = product [2 / aux x | x <- [0..n]]

where

aux 0 = 1

aux 1 = sqrt 2

aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = product [2/x | x <- 1 : xs]

where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi

aproximacionPi3 :: Int -> Double

aproximacionPi3 n = product (2 : take n (map (2/) xs))

where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi

errorPi :: Double -> Int

errorPi x = head [n | n <- [1..]

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x = until aceptable (+1) 1

where aceptable n = abs (pi - aproximacionPi n) < x

Primo suma de dos cuadrados

PorJosé A. Alonso 14-marzo-20161-abril-2016

Definir la sucesión

   primosSumaDe2Cuadrados :: [Integer]

1	primosSumaDe2Cuadrados :: [Integer]

cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,

   λ> take 20 primosSumaDe2Cuadrados
   [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]
   λ> primosSumaDe2Cuadrados !! (2*10^5)
   5803241

λ> take 20 primosSumaDe2Cuadrados

[2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]

λ> primosSumaDe2Cuadrados !! (2*10^5)

5803241

En el ejemplo anterior,

13 está en la sucesión porque es primo y 13 = 2²+3².
11 no está en la sucesión porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2²=7 y 11-3²=2 no son cuadrados).
20 no está en la sucesión porque, aunque es suma de dos cuadrados (20=4²+2²), no es primo.

Soluciones

import Data.Numbers.Primes (primes)

-- 1ª solución
-- ===========

primosSumaDe2Cuadrados1 :: [Integer]
primosSumaDe2Cuadrados1 =
    [n | n <- primes,
         esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool
esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]
sumas2cuadrados n = 
    [(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],
             let z = n - x^2,
             esCuadrado z, 
             let y = raiz z,
             x <= y]
             
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
    where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))

-- 2ª solución
-- ===========

primosSumaDe2Cuadrados2 :: [Integer]
primosSumaDe2Cuadrados2 =
    2 : [n | n <- primes,
             n `mod` 4 == 1]

-- Comparación de eficiencia
-- =========================

--    λ> primosSumaDe2Cuadrados1 !! (2*10^3)
--    38153
--    (3.03 secs, 568,239,744 bytes)
--    λ> primosSumaDe2Cuadrados2 !! (2*10^3)
--    38153
--    (0.05 secs, 20,017,912 bytes)

import Data.Numbers.Primes (primes)

-- 1ª solución

-- ===========

primosSumaDe2Cuadrados1 :: [Integer]

primosSumaDe2Cuadrados1 =

[n | n <- primes,

esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool

esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]

sumas2cuadrados n =

[(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],

let z = n - x^2,

esCuadrado z,

let y = raiz z,

x <= y]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado 25 == True

-- esCuadrado 26 == False

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz 25 == 5

-- raiz 24 == 4

-- raiz 26 == 5

raiz :: Integer -> Integer

raiz x = floor (sqrt (fromIntegral x))

-- 2ª solución

-- ===========

primosSumaDe2Cuadrados2 :: [Integer]

primosSumaDe2Cuadrados2 =

2 : [n | n <- primes,

n `mod` 4 == 1]

-- Comparación de eficiencia

-- =========================

-- λ> primosSumaDe2Cuadrados1 !! (2*10^3)

-- 38153

-- (3.03 secs, 568,239,744 bytes)

-- λ> primosSumaDe2Cuadrados2 !! (2*10^3)

-- 38153

-- (0.05 secs, 20,017,912 bytes)

Referencias

N.J.A. Sloane, Sucesión A002313 de la OEIS.
M. Bates, Primes of the form x² + ny²–
G. Xiao, Two squares.

Codificación matricial

Soluciones

Números de Catalan

Soluciones

Caminos minimales en un arbol numérico

Soluciones

Cálculo de pi usando la fórmula de Vieta

Soluciones

Primo suma de dos cuadrados

Soluciones

Referencias

Entradas recientes

Buscar

Correo electrónico